[BOJ] 14889: 스타트와 링크 (JAVA)

문제

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

 

풀이

N명을 N / 2명씩 두 개의 팀으로 나눠야 한다. 즉, N명 중에서 N / 2명을 고르는 것(순서 상관X)이므로 조합을 사용하면 된다. 

 

DFS 메서드(재귀)를 통해 N / 2명을 다 고른 후, 스타트 팀의 능력치와 링크 팀의 능력치를 구해야 한다. N / 2명을 고를 때 이미 방문 처리를 했으므로 방문 처리한 것은 스타트 팀, 하지 않은 것은 링크 팀으로 구분하면 된다.

• 스타트 팀: used[i] = true
• 링크 팀: used[i] = false

 

스타트 팀과 링크 팀의 능력치를 계산한 후, 두 팀의 능력치 차이를 최소값과 비교해 갱신하면 된다.

 

코드

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

public class BOJ_14889 {

	static int N, ans;
	static int[][] arr;
	static boolean[] used;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

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

		// n C n/2
		ans = Integer.MAX_VALUE;
		dfs(0, 0);
		System.out.println(ans);
	}

	static void dfs(int depth, int start) {
		if (depth == N / 2) {
			int startScore = 0, linkScore = 0;
			// 스타트 팀의 능력치 구하기 (used[i]가 true)
			for (int i = 0; i < N - 1; i++) {
				if (!used[i]) continue;
				for (int j = i + 1; j < N; j++) {
					if (!used[j]) continue;
					startScore += arr[i][j] + arr[j][i];
				}
			}

			// 링크 팀의 능력치 구하기 (used[i]가 false)
			for (int i = 0; i < N - 1; i++) {
				if (used[i]) continue;
				for (int j = i + 1; j < N; j++) {
					if (used[j]) continue;
					linkScore += arr[i][j] + arr[j][i];
				}
			}
			ans = Math.min(ans, Math.abs(startScore - linkScore));
			return;
		}

		for (int i = start; i < N; i++) {
			if (used[i])
				continue;

			used[i] = true;
			dfs(depth + 1, i);
			used[i] = false;
		}
	}
}

 

여담

조합을 구할 때 시작점을 주는 것을 까먹었다. 그래서 당연하게도 시간초과를 맞이했다...ㅎㅎ

반복문을 돌릴 때 순열은 0부터, 조합은 start부터 시작한다는 것을 까먹지 말자....!!

 

그리고 스타트 팀과 링크 팀의 능력치를 구하는 부분에서 어떻게 해야할지 많은 고민을 했다. 선택한 것의 합을 구하는 것은 해봤지만 선택하지 않은 것의 합까지 구하는 것은 처음이었..

 

아무튼 방문 배열을 사용해서 스타트 팀과 링크 팀을 구분하도록 했다. 만약 구해야 하는 팀이 하나 더 늘어난다면 boolean 타입이 아닌 int 타입으로 선언해서 구분하면 될 것 같다. 

---