문제

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

---

입력

첫째 줄에 N이 주어진다.
둘째 줄부터 N개의 줄에 S가 주어진다.
각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다.

---

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

---

풀이

제한조건

• N(4 ≤ N ≤ 20, N은 짝수)
• Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

접근방법

순열

문제를 해결하는 과정은 아래의 반복이다.

1. 순열 생성
2. 각 팀의 점수 계산
3. 최소 차 구하기

순열을 통해 팀을 구성해보자.
각 팀은 전체의 절반 인원으로만 구성되기에 종료조건이 매우 단순하다.

private static void permutaion(int start, int depth) {
	if (depth == N / 2) {
		return;
	}
	for (int i = start; i < N; ++i) {
	if (check[i])
		continue;
	check[i] = true;
	permutaion(i, depth + 1);
	check[i] = false;
	}
}

이제 각 팀의 점수를 구해야 한다.
먼저 선택된 팀의 경우 check[i]가 true로 변경되어 있다.
즉 check 배열에 절반은 true, 나머지 절반은 false로 저장되어 있고
이는 즉 동일한 값을 가지는 index가 한 팀이라는 말이다.

check 배열을 이중 For문을 통해 순회하며, 한 팀인 사람들의 시너지 정보를 확인해주자.

private static int getSum(boolean flag) {
	int sum = 0;
    for (int i = 0; i < N; ++i) {
    	if (check[i] == flag)
        	continue;
        for (int j = 0; j < N; ++j) {
			if (check[j] == flag)
				continue;
			sum += arr[i][j];
		}
	}
	return sum;
}

이제 구한 점수를 기반으로 팀의 최소차를 계산해 본다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, min;
	static int[][] arr;
	static boolean[] check;

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

		arr = new int[N][N];
		check = new boolean[N];

		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			for (int j = 0; j < N; ++j) {
				arr[i][j] = stoi(inputs[j]);
			}
		}

		min = Integer.MAX_VALUE;
		permutaion(0, 0);
		System.out.println(min);
	}

	private static void permutaion(int start, int depth) {
		if (depth == N / 2) {
			int team1 = getSum(false);
			int team2 = getSum(true);
			min = Math.min(min, Math.abs(team2 - team1));
			return;
		}
		for (int i = start; i < N; ++i) {
			if (check[i])
				continue;
			check[i] = true;
			permutaion(i, depth + 1);
			check[i] = false;
		}
	}

	private static int getSum(boolean flag) {
		int sum = 0;
		for (int i = 0; i < N; ++i) {
			if (check[i] == flag)
				continue;
			for (int j = 0; j < N; ++j) {
				if (check[j] == flag)
					continue;
				sum += arr[i][j];
			}
		}
		return sum;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}