[BOJ] 14889. 스타트와 링크(비트마스크 풀이)

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

14889번: 스타트와 링크

앞에서 dfs로 풀었던 문제이지만 비트 마스크를 연습할 겸 다시 풀어보았다.

0부터 (1<<n)-1 까지의 모든 경우를 구하고 (1 << k)를 이용해서 각 자리의 수가 0이면 해당 자리는 1번 팀에 1이면 2번 팀에 넣어주도록 했다.

000111처럼 정확히 n/2로 0과 1이 나눠진 경우에만 능력치의 합을 계산해준다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int n;
int s[20][20];
vector<int> t1;
vector<int> t2;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    }
 
    int ans = -1;
    for (int i = 0; i < (1<<n); i++) {
        
        t1.clear();
        t2.clear();
 
 
        //0인 경우 t1에 그렇지 않은 경우 t1에 넣는다.
        for (int k = 0; k < n; k++) {
            if ((i & (1 << k)) == 0) {
                t1.push_back(k);
            }
            else {
                t2.push_back(k);
            }
        }
 
 
        //팀이 반으로 나눠지지 않은 경우 skip
        if (t1.size() > n / 2) continue;
        if (t2.size() > n / 2) continue;
 
 
        int t1sum = 0;
        int t2sum = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j) continue;
                t1sum += s[t1[i]][t1[j]];
                t2sum += s[t2[i]][t2[j]];
            }
        }
 
 
        int diff = t1sum - t2sum;
        if (diff < 0) diff = -diff;
        if (ans == -1 || ans > diff) ans = diff;
 
    }
 
    cout << ans << '\n';
 
    return 0;
}