[BaekJoon] 14899 백준 스타트와 링크

import java.util.*;

public class Main {	
	static int[][] arr;
	static int n;
	static int[] visited;
	static int min = Integer.MAX_VALUE;
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		arr = new int[n][n];
		
		visited = new int[n];
		
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		
		dfs(0, 0);
		
		System.out.println(min);
		
	}
	
	public static void dfs(int index, int count) {
		if(index >= n) return;
		if(count > n/2) return;
		
		if(count == n/2) {
			int t1 = 0; int t2 = 0;
			for(int i = 0; i<n; i++) {
				if(visited[i] == 1) {
					for(int j = 0; j<n; j++) {
						if(visited[j] == 1)
							t1 += arr[i][j];
					}
				}
				
				else if(visited[i] == 0) {
					for(int j = 0; j<n; j++) {
						if(visited[j] == 0)
							t2 += arr[i][j];
					}
				}
			}
			
			if(Math.abs(t1-t2) < min)
				min = Math.abs(t1-t2);
		
			return;
		}
		
		visited[index] = 1;
		dfs(index+1, count+1);
		
		visited[index] = 0;
		dfs(index+1, count);
		
	}
	
}

 

SW Expert Academy 의 요리사와 똑같은 문제다. 

 

팀을 정확히 반으로 가르기 때문에 N/2의 팀원을 구한후에 팀 별로 점수를 계산하면 된다. 

 

 

내가 1팀에 속했을 때와 0팀에 속했을 때로 재귀를 호출해가며 count가 N/2가 되면 각각 2팀으로 나누어졌다는 뜻이기에 서로 같은 숫자 (1, 0)을 가진 사람끼리 점수를 더해주면 된다.