14889번: 스타트와 링크

14889번: 스타트와 링크

사용 언어: C++

 

문제 요약

총 N명의 사람이 있고, 이들을 두 팀(스타트 팀, 링크 팀)으로 나눈다. 각 팀에 속한 사람들의 능력치 합 차이를 최소화하는 것이 목표.

• 능력치는 2차원 배열 S[i][j]로 주어지며,
  i번과 j번이 같은 팀일 때 더해지는 값은 S[i][j] + S[j][i].
• N은 항상 짝수이며, 두 팀은 N/2명씩 구성돼야 함.

풀이

1. 조합을 통해 팀을 나눈다

• N명 중 N/2명을 선택해서 스타트 팀을 구성하면,
• 나머지 인원은 자동으로 링크 팀이 된다.
  → 즉, 전체 경우의 수는 NC(N/2) 개의 조합.

2. 각 조합에 대해 능력치 차이 계산

• 스타트 팀의 능력치 = sum(S[i][j] + S[j][i]) (for i, j in 스타트 팀)
• 링크 팀도 동일하게 계산
• 두 팀의 차이의 절댓값을 구해 최소값을 갱신한다

3. 백트래킹으로 조합 구성

• 중복 없이 N/2명 뽑기 위해 next 인덱스를 통해 재귀적으로 조합 생성

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int N, S[21][21], ans = 1e9;
vector<int> team;

void dfs(int idx, int depth) {
    if (depth == N / 2) {
        vector<int> start, link;

        for (int i = 0; i < N; i++) {
            if (find(team.begin(), team.end(), i) != team.end())
                start.push_back(i);
            else
                link.push_back(i);
        }

        int startSum = 0, linkSum = 0;
        for (int i = 0; i < N / 2; i++) {
            for (int j = 0; j < N / 2; j++) {
                startSum += S[start[i]][start[j]];
                linkSum += S[link[i]][link[j]];
            }
        }

        ans = min(ans, abs(startSum - linkSum));
        return;
    }

    for (int i = idx; i < N; i++) {
        team.push_back(i);
        dfs(i + 1, depth + 1);
        team.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> S[i][j];

    dfs(0, 0);
    cout << ans;
    return 0;
}