백준 14889 : 스타트와 링크

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

14889번: 스타트와 링크

[ 문제풀이 ]

간단한 문제이다. N명의 사람 중 N/2명의 사람을 뽑는 조합을 구현할 수 있다면 아주 쉽게 해결할 수 있는 문제이다.

​다만, 모든 조합을 구할 필요가 없다. 6명의 사람 중 3명을 뽑는 모든 조합을 한번 보자.

자세히 보면 1번 사람을 선택한 후 가능한 조합 이후로는 이미 앞에서 구한 조합들만 나오는 것을 확인할 수 있다. 따라서 우리는 모든 조합을 구할 필요 없이 1번 사람을 포함하는 조합만 구하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, half, answer;
	static int[][] S;
	static boolean[] check;
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		answer = (int)1e9;
		half = N >> 1;
		S = new int[N][N];
		check = new boolean[N];
		
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; ++j) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		check[0] = true; //0번 사람을 무조건 선택
		pickTeam(1, 1); //1번 사람부터 조합을 구함

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}

	
	public static void pickTeam(int idx, int size) {
		if (size == half) {
			answer = Math.min(answer, getAnswer());
			return;
		}

		for (int i = idx; i < N; ++i) {
			check[i] = true;
			pickTeam(i + 1, size + 1);
			check[i] = false;
		}
	}

	public static int getAnswer() {
		int teamA = 0, teamB = 0;
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				//teamA = i와 j번 사람이 모두 true인 값
				if (check[i] && check[j]) teamA += S[i][j];
				//teamA = i와 j번 사람이 모두 false인 값
				if (!check[i] && !check[j]) teamB += S[i][j];
			}
		}
		
		return Math.abs(teamA - teamB);
	}
}