BOJ 14889. 스타트와 링크

• 문제링크 : https://www.acmicpc.net/problem/14889

---

문제 요약

짝수 N명을 N/2명씩 두 팀으로 나눈다. i번과 j번 사람이 같은 팀이면 그 팀의 능력치에 S[i][j]와 S[j][i]가 모두 더해지고, S[i][j]와 S[j][i]는 다를 수 있다. 팀의 능력치는 팀 안 모든 쌍의 값을 더한 것이다. 두 팀 능력치 차이의 최솟값을 구한다.

---

1. 문제 해석

• N명을N/2명씩두팀으로나누려고한다.(4≤N≤20,N은짝수) • 두팀의능력치를구한다음,차이의최소값을구하는문제 • S[i][j]=i번사람과j번사람이같은팀에속했을때,팀에더해지는능력치 • 팀의능력치:팀에속한모든쌍의S[i][j]의합

• go(index,first,second) • index번째 사람을 어떤 팀에 넣을지 결정해야 함 • 1번 팀과 2번 팀에 속한 사람이 각각 first, second에 들어 있음

• 정답을찾은경우 • index == n

• 불가능한경우 • first의 크기 > n/2 • second의 크기 > n/2

• 다음경우 • 1번 팀: go(index, first, second) • 2번 팀: go(index, first ,second) • 두경우모두호출전에first또는second에index를넣고,호출후에빼는과정이필요

---

2. 문제 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int n;
int go(int index, vector<int> &first, vector<int> &second) {
    if (index == n) {
        if (first.size() != n/2) return -1;
        if (second.size() != n/2) return -1;
        int t1 = 0;
        int t2 = 0;
        for (int i=0; i<n/2; i++) {
            for (int j=0; j<n/2; j++) {
                if (i == j) continue;
                t1 += s[first[i]][first[j]];
                t2 += s[second[i]][second[j]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        return diff;
    }
    int ans = -1;
    first.push_back(index);
    int t1 = go(index+1, first, second);
    if (ans == -1 || (t1 != -1 && ans > t1)) {
        ans = t1;
    }
    first.pop_back();
    second.push_back(index);
    int t2 = go(index+1, first, second);
    if (ans == -1 || (t2 != -1 && ans > t2)) {
        ans = t2;
    }
    second.pop_back();
    return ans;
}
int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> first, second;
    cout << go(0, first, second) << '\n';
}