백준 14889번 스타트와 링크 문제 풀이

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

백준저지 14889번 스타트와 링크 문제 풀이이다.

N값이 크지 않으므로 dfs를 통한 완전 탐색으로 문제 해결이 가능하다.

다음은 풀이 코드이다.

 

#include <bits/stdc++.h>

using namespace std;

bool team[20];
int n;
int s[20][20];
int ans;
int abs(int v) {
    if (v<0) return -v;
    else return v;
}
void check() {
    int start=0;
    int link=0;
    vector<int> ss, ll;
    ss.reserve(n/2);
    ll.reserve(n/2);
    for (int i=0; i <n; i++) {
        if (team[i]) {
            ss.push_back(i);
        } else {
            ll.push_back(i);
        }
    }
    for (int i=0; i < n/2; i++) {
        for (int j=0; j < n/2; j++) {
            if (i==j) continue;
            start += s[ss[i]][ss[j]];
        }
    }
    for (int i=0; i < n/2; i++) {
        for (int j=0; j < n/2; j++) {
            if (i==j) continue;
            link += s[ll[i]][ll[j]];
        }
    }
    ans = min(ans, abs(start-link));
}
void dump() {
    for (int i=0; i < n; i++) {
        cout << team[i] << ", ";
    }
    cout << '\n';
}
void dfs(int i, int j) {
    if (j > n-i) return;
    if (i >= n) {
        if (j == 0) {
            // dump();    
            check();
        }
        return;
    }
    team[i] = true;
    dfs(i+1, j-1);
    team[i] = false;
    dfs(i+1, j);
}
int main() {
    ans = 987654321;
    cin >> n;
    for (int i=0; i < n; i++) {
        for (int j=0; j < n;j++) {
            cin >> s[i][j];
        }
    }
    dfs(0, n/2);
    cout << ans << '\n';
    return 0;
}