백준 14889 스타트와 링크 (Java)

1. 문제 링크

14889번: 스타트와 링크

 

2. 문제 및 입출력예제

 

3. 문제 풀이

팀을 N/2명으로 나누는 조합 과정을 거친다.

뽑힌 사람은 T1, 안 뽑힌 사람을 T2 배열로 나눠서 넣는다.

각 팀원끼리의 능력치를 전부 더하고, 차이가 최소가 되는 값을 출력한다.

 

SWEA의 요리사 문제와 유사하다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N, human[][], numbers[], result, first;
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();
       
       N = Integer.parseInt(br.readLine());
       human = new int[N][N];
       numbers = new int[N/2];
       for(int i=0;i<N;i++) {
    	   String[] split = br.readLine().split(" ");
    	   for(int j=0;j<N;j++) {
    		   human[i][j] = Integer.parseInt(split[j]);
    	   }
       }
       
       //조합
       result = Integer.MAX_VALUE;
       Combination(0, 0);
       
       
       System.out.println(result);
	}

	private static void Combination(int cnt, int start) {
		if(cnt == N/2) {
			int[] T1 = new int[N/2];
			int[] T2 = new int[N/2];
			int sum1 = 0, sum2 = 0;
			boolean[] visit = new boolean[N];
			
			for(int i=0;i<N/2;i++) {
				T1[i] = numbers[i];
				visit[numbers[i]] = true;
			}
			int idx = 0;
			for(int i=0;i<N;i++) {
				if(!visit[i]) {
					T2[idx++] = i;
				}
			}
			
			for(int i=0;i<N/2;i++) {
				for(int j=i; j<N/2; j++) {
					sum1+= human[T1[i]][T1[j]]+human[T1[j]][T1[i]];
					sum2+= human[T2[i]][T2[j]]+human[T2[j]][T2[i]];
				}
			}
			
			result = Math.min(result, Math.abs(sum1-sum2));
			return;
		}
		for(int i=start;i<N;i++) {
			numbers[cnt] = i;
			Combination(cnt+1, i+1);
		} 		
	}
}