[삼성 기출 문제] 백준 14889 스타트와 링크

문제 링크

클릭시 이동합니다.

어떻게 풀까?

를 구하는 문제입니다.

n 개의 데이터를 스타트 팀, 링크 팀에 넣은 뒤에 두 팀의 능력치를 계산해서 두 능력치의 차이 중 최소의 값을 출력합시다!

참고로, 

능력치는 입력에 주어지는 것 처럼 2차원 배열에 저장하실 겁니다!

팀의 능력치를 구할 때, i, j가 같은 팀이면 능력치를 (i,j)와 (j,i)의 합으로 구할 수 있습니다!

즉, 1번 사람과 2번 사람이 팀이라면, (1,2)와 (2,1)를 더해서 구하면 됩니다!

2차원 for문을 이용하면 1번 사람과 2번 사람의 경우와 2번 사람과 1번 사람의 경우 두 개를 중복으로 확인할 것입니다.

이를 피하기 위해서 j는 i+1번 번호 부터 확인하도록 합시다!

저는 비트조합을 이용해서 조합을 구했는데, 이를 확인하시려면 제가 예전에 올렸던 http://sangdo913.tistory.com/7 를 참고하도록 합시다.

코드

#include<iostream>
 
using namespace std;
 
int ABS(int i1){return i1 > 0 ? i1 : -i1;}
int MIN(int i1, int i2){return i1 < i2 ? i1 : i2;}
 
int arr[20][20], n;
 
int f(int selected){
    int team[2] = {0,0};
    for(int i = 0; i < n; i++){
        bool t1 = selected & (1 << i); 
        for(int j = i + 1; j < n; j++){
            bool t2 = selected & (1<<j);
            if(t1 == t2){
                team[t1]+= arr[i][j] + arr[j][i];
            }
        }
    }
    return ABS(team[0]-team[1]);
}
 
int getZero(int bit){
    int res = 0;
    while((bit & 1) == 0) res++, bit >>= 1;
    return res;
}
 
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> arr[i][j];
 
    int bit = (1 << (n/2))-1;
    int res = 0x7fffffff;
 
    while(bit < (1 << n)){
        int temp = bit | ((-bit & bit)-1);
        res = MIN(f(bit), res); 
        
        int nextBit = (temp + 1) | (((~temp & -~temp) -1 ) >> (getZero(bit)+1));
        bit = nextBit;
    }
 
    cout << res;
    return 0;
}

시간복잡도

이므로, 시간복잡도는 이긴 한데... 이걸 어떻게 간단하게 할 수 있을까요..?

어쨌든, 보다는 작습니다!