백준14889 : 스타트와 링크

백준14889 : 스타트와 링크

문제

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

i멤버와 j멤버가 같은 팀에 있을 때에 갖는 능력치 배열 Sij가 주어졌을 때, N명의 멤버를 스타트팀과 링크팀 절반으로 나누었을 때 각 팀 능력치 차의 최솟값을 구하는 문제

접근방법

1. N명 중 N/2명을 고르는 combination 함수를 이용한다.

   • N명 중 N/2명을 골라 스타트팀에 넣으면 선택되지 않은 멤버는 링크팀에 속하게 된다.

   • nCr의 조합 경우의 수를 출력하는 것은 아래의 함수를 이용하였다.

   static void combination(int[] arr, int index, int n, int r, int target){
       if(r == 0){
           /* 선택할 r개를 고를 때 마다 실행되는 부분 */
       }else if(target == n){
           return;
       }else {
           arr[index] = target;
           combination(arr, index+1, n, r-1, target+1);
           combination(arr, index, n, r, target +1);
       }
   }

• if(r == 0) 부분이 실행되면 배열 arr에 선택한 r개가 담긴다. 이 함수에 담긴 인덱스들은 start[] 배열에 저장하고, 여기에 담기지 않은 인덱스들은 link[] 배열에 저장한다.

  • 구분해주기 위해 boolean check[] 배열을 이용하였다.

• 이 때, 조합을 절반만 구하면 나머지 절반은 자동으로 다른 팀으로 정해지기 때문에 nCr을 구하는 함수를 절반만 실행하면 된다.

  예를 들어 4C2는 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)가 되는데, (1,2) 를 추출하면 (3,4)는 자동으로 다른 팀이 되므로, (1,2) (1,3) (1,4) 만 구하면된다. 즉, nCr/2 만큼만 조합 경우의 수를 계산하는 함수를 실행해주면 된다.

2. 각 팀의 능력치를 계산한다.

   • 예를 들어 (2, 3, 5) 와 (1, 4, 6) 으로 팀을 나누었을 때, 스타트팀의 능력치는 S(2,3) + S(3,2) + S(2,5) + S(5,2) + S(3,5) + S(5,3)이 된다.

   • 이를 계산해주기 위해 for문을 사용하였다.

     for(int i=0; i<N/2; i++)
         for(j=i+1; j<N/2; j++){
             start_stat += S[start[i]][start[j]] + S[start[j]][start[i]];
             link_stat += S[link[i]][link[j]] + S[link[j]][link[i]];
         }

3. 계산한 능력치의 최소차를 구한다.

소스코드

import java.io.*;
import java.util.*;
​
public class Main{
​
    static int N;
    static int S[][];
    static int min_statDiff;
    static int count;
​
    // nCr 개수
    static int combb(int n, int r) {
        if(n == r || r == 0)
            return 1;
        else
            return combb(n - 1, r - 1) + combb(n - 1, r);
    }
​
    static void combination(int[] arr, int index, int n, int r, int target){
        if(r == 0){
            if(count > 0){  // nCr / 2 만큼만 조합 경우의 수 구하기
                int cur_statDiff = calcStat(arr);
                if(min_statDiff == -1 || cur_statDiff < min_statDiff)
                    min_statDiff = cur_statDiff;
                --count;
            }
        }else if(target == n){
            return;
        }else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1);
            combination(arr, index, n, r, target +1);
        }
    }
​
    static int calcStat(int[] start){
        boolean check[] = new boolean[N];
        int[] link = new int[N/2];
​
        for(int i=0; i<N/2; i++)
            check[start[i]] = true;
        int j = 0;
        for(int i=0; i<N; i++)
            if(check[i] == false)
                link[j++] = i;
​
        int start_stat = 0;
        int link_stat = 0;
​
        for(int i=0; i<N/2; i++)
            for(j=i+1; j<N/2; j++){
                start_stat += S[start[i]][start[j]] + S[start[j]][start[i]];
                link_stat += S[link[i]][link[j]] + S[link[j]][link[i]];
            }
        return Math.abs(start_stat - link_stat);
    }
​
​
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        N = Integer.parseInt(in.readLine());
        S = new int[N][N];
        int combi_set[] = new int[N/2];
​
        for(int i=0; i<N; i++){
            String line[] = in.readLine().split(" ");
            for(int j=0; j<N; j++)
                S[i][j] = Integer.parseInt(line[j]);
        }
​
        count = combb(N, N/2)/2;
        min_statDiff = -1;
        combination(combi_set, 0, N, N/2, 0 );
​
        System.out.println(min_statDiff);
​
    }
}