[백준] 15661 링크와 스타트

 

완전탐색을 이용해 부분집합을 만들어보면 된다

비트를 이용해보자 편하게!

 

0~(1<<n)까지보며 비트가 1인팀 , 0인팀으로 나눈다

 

그리고 팀의 점수를 직접 구해보고 비교하면 된다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int a[22][22], ans = 1e9;
int r[22], l[22],rc,lc;
 
void solve() {
    int s = 0,e=0;
    for (int i = 0; i < rc; i++) {
        for (int j = 0; j < rc; j++) {
            s += a[r[i]][r[j]];
        }
    }
    for (int i = 0; i < lc; i++) {
        for (int j = 0; j < lc; j++) {
            e += a[l[i]][l[j]];
        }
    }
    ans = min(ans, abs(s - e));
}
 
int main() {
    int n; scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf(" %d", &a[i][j]);
        }
    }
 
    for (int i = 0; i < (1 << n); i++) {
        memset(r, 0, sizeof(r)); memset(l, 0, sizeof(l));
        rc = 0, lc = 0;
        for (int j = 0; j < n; j++) {
            if (i&(1 << j)) r[rc++] = j;
            else l[lc++] = j;
        }
        solve();
    }
    printf("%d\n", ans);
}