백준 스타트와 링크(14889)

 

오늘은 백트래킹 문제를 풀어보았다.

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

해당 문제는 어떻게 푸는게 좋을지 생각을 해보자

 

 

1. A팀의 인원을 선별하게 되면 나머지는 자동적으로 B팀이라고 가정하면 된다.

 

2. A팀을 예시로 1 2 5로 뽑나, 5 2 1 로 뽑나 같은 경우의 수로 해당 중복 케이스는 진행하지 않는 방향으로 구성하면 된다.

 

하여 뽑힌 A팀의 인원의 능력치와 B팀의 능력치를 구하여 비교한 최소값을 해로 구하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int answer = Integer.MAX_VALUE;
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        solution();
    }


    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        boolean[] team = new boolean[N];

        for (int i=0 ; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        backtracking(-1, team, N/2);

        System.out.println(answer);
    }

    public static void backtracking(int prev, boolean[] team, int count) {
        if (count == 0) {
            int scoreA = 0;
            int scoreB = 0;

            for (int i=0; i < N; i++) {
                if (team[i]) {
                    scoreA += add(team, team[i], i);
                } else {
                    scoreB += add(team, team[i], i);
                }
            }

            answer = Math.min(answer, Math.abs(scoreA - scoreB));
            return;
        }

        for (int i=prev+1; i < N; i++) {
            team[i] = true;
            backtracking(i, team, count - 1);
            team[i] = false;
        }

    }

    public static int add(boolean[] team, boolean type, int num) {
        int score = 0;
        for (int i=0; i < N; i++) {
            if (team[i] == type) {
                score += map[num][i];
            }
        }
        return score;
    }

}

 

결과