[백준] 14889번 : 스타트와 링크

문제

 

 

접근 방식

짝수 명의 직원들을 절반씩 나누어 두 팀으로 구성할 때

두 팀의 능력치 차이가 가장 적은 경우를 구해야 한다.

 

각 팀을 모두 조합할 필요는 없고 한 팀만 구해도 되는데

한쪽팀만 구하면 반대팀은 자동으로 구성되기 때문이다.

 

백트래킹을 이용해 절반인 n/2까지 재귀를 호출하며

팀을 짜주고 n/2일 때 현재까지 기록으로

각 팀간의 점수차를 구해주면 된다.

 

즉, 절반의 팀을 구하는 메서드와

각 팀의 점수를 계산하고 차이를 구하는 메서드가 필요하다.

 

풀이

class Main {
    
    static int n, m;
	static int min = Integer.MAX_VALUE;
	static int[][] stats;
	static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		m = n/2;

		stats = new int[n][n];
		isUsed = new boolean[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				stats[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		solve(0, 0);

		System.out.println(min);
	}

	static void solve(int s, int start) {
		if (s == m) {
			calculate();
			return;
		}

		for (int i = start; i < n; i++) {
			if (isUsed[i]) continue;
			if (s == 0 && i > 0) break;
			isUsed[i] = true;
			solve(s + 1, i + 1);
			isUsed[i] = false;
		}
	}

	static void calculate() {
		int start = 0;
		int link = 0;

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (isUsed[i] == isUsed[j]) {
					if (isUsed[i]) {
						start += (stats[i][j] + stats[j][i]);
					} else {
						link += (stats[i][j] + stats[j][i]);
					}
				}
			}
		}

		min = Math.min(min, Math.abs(start - link));
	}
}