[BOJ] 14889. 스타트와 링크

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

14889번: 스타트와 링크

각 팀원들의 능력치가 주어지고 두 팀의 능력치 차이가 최소가 되는 팀을 구해서

그 차이 값을 출력하는 문제이다.

 

 

 N(4 ≤ N ≤ 20, N은 짝수)이므로 팀원을 나누는 모든 경우를 해보는 완전 탐색으로 풀어줄 수 있다.

N명의 팀원을 1번 팀에 들어가는 경우와 2번 팀에 들어가는 경우를 모두 해준다.

단, 모든 팀원들의 팀을 정했을 때 팀원이 N/2가 아닌 경우는 계산해주지 않는다(return)

이 부분을 제대로 처리해주지 않아서 오류가 났었다...ㅠ

능력치를 계산해주는 부분에서 vector의 index를 넘어갔기 때문이다.

 

 

모든 팀원의 팀을 정해주었고, 각 팀에 N/2명씩 들어있으면 각 팀의 능력치를 계산해준다.

두 팀의 능력치의 차이를 구해서 그 차이의 최솟값이 정답이다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int n, ans;
int s[20][20];
 
vector<int> t1;
vector<int> t2;
 
int calc() {
    int diff;
    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]];
        }
    }
 
 
    //차이를 구한 후 차이 값을 리턴
    diff = t1sum - t2sum;
    if (diff < 0) diff = -diff;
 
    return diff;
}
 
 
//팀을 골라준다.
void select(int index) {
 
    //팀을 모두 고른 경우
    if (index == n) {
        //각 팀은 N/2명이어야 하므로 그렇지 않은 경우 리턴
        if (t1.size() > n / 2) return;
        if (t2.size() > n / 2) return;
 
 
        //각 팀의 능력치 차이를 계산해서 최소값과 비교한다.
        int tmp = calc();
        if (ans == -1 || ans > tmp) ans = tmp;
        
        return;
    }
 
 
    //index번째를 첫번쨰 팀에 넣는 경우
    t1.push_back(index);
    select(index + 1);
    t1.pop_back();
 
 
    //index번째를 두번째 팀에 넣는 경우
    t2.push_back(index);
    select(index + 1);
    t2.pop_back();
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    }
 
 
    ans = -1;
    select(0);
 
    cout << ans;
 
    return 0;
}