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

 

 

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

문제 출처 : 링크

14889번: 스타트와 링크

삼성 SW역량테스트 기출 문제다.

정답률도 매우 높고, 실제로 다른 기출문제에 비해 상당히 쉬운편이다.

 

짝수로 주어진 사람 수를 2팀으로 나누고, 문제에 주어진 능력치 값을 구해 두 팀의 최소차를 출력해주면 된다.

 

조합을 짤 수만 있다면 간단히 해결이 가능하다.

 

조합에서 팀이 나누어지는 상황마다 각 팀의 능력치 값을 구하고 절대값을 구한다. 이 절대값 중 가장 작은 값을 출력하면 끝!

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_14889_스타트와링크 {
 
    static int N;
    static int[][] map;
    static boolean[] num;
    
    static int[] arr;
    static int[] set;
    static int r;
    static int min;
    
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        arr = new int[N];
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        
        r = N/2;
        set = new int[r];
        min = Integer.MAX_VALUE;
        comb(0,0);
        
        System.out.println(min);
    }
 
    public static void comb(int len, int k) {
        
        if(len == r) {
            num = new boolean[N];
            for (int i = 0; i < set.length; i++) {
                num[set[i]] = true;
            }
            
            int start = 0;
            int link = 0;
            
            for (int i = 0; i < num.length; i++) {
                if(num[i]) { // start 팀
                    for (int j = 0; j < num.length; j++) {
                        if(i==j) continue;
                        if(num[j]) {
                            start += map[i][j];
                        }
                    }
                }
                
                else { // link 팀
                    for (int j = 0; j < num.length; j++) {
                        if(i==j) continue;
                        if(!num[j]) {
                            link += map[i][j];
                        }
                    }
                }
            }
            
            int res = Math.abs(start-link);
            if(min > res) min = res;
            return;
        }
        
        if(k == N) return;
        
        set[len] = arr[k];
        comb(len+1, k+1);
        comb(len, k+1);
    }
}