[BOJ/백준 14889][C++] 스타트와 링크

문제

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

백준 14889

백준 14889

 

문제 내용

N명을 2개의 팀으로 나눈 후, 각 팀의 능력치를 구한다.

각 팀의 능력치 차가 최소가 되는 값을 구하면 된다.

이때 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합이다. (아래는 예시) 

1,2번이 같은 팀이고 3,4번이 같은 팀일 때
(1,2)가 속한 팀의 능력치 = arr[1][2]+arr[2][1]
(3,4)가 속한 팀의 능력치 = arr[3][4]+arr[4][3]

 

문제 풀이

이 문제에서 가장 중요한 부분은, 팀을 두 개로 나누는 것이다.

이 부분을 위해 백트래킹으로 문제를 풀었다.

사람은 1~n번으로 주어지고, 순서가 의미가 없기 때문에 N과 M (2)를 참고하면 좋을 것 같다.

[BOJ/백준 15650][C++] N과 M (2)

백트래킹 함수의 종료 조건을 cnt가 n/2가 되었을 때로 설정했다. (팀을 두개로 나눈 경우이다)

이후, 각 팀의 능력치를 구하여, 최솟값을 갱신해 나가면 된다.

팀을 구분하는 방법은 used배열을 그대로 사용하면 되는데, 종료조건일 때 used배열의 n/2개 원소는 true, 나머지 n/2개의 원소는 false로 되어있다는 점을 이용하면 된다. 

 

코드

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

int arr[21][21];
bool used[21];

int n;
int minGap = 2005;

// 팀을 나누는 함수 - used 배열(true/false)로 팀 구분
void back(int cnt, int before) {
    if (cnt == n / 2) {
        int aSum = 0;
        int bSum = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;

                if (used[i] && used[j]) { // a팀
                    aSum += (arr[i][j] + arr[j][i]);
                } else if (!used[i] && !used[j]) { // b팀
                    bSum += (arr[i][j] + arr[j][i]);
                }
            }
        }

        /**
         * (1,3)이 같은 팀일 때, 위의 for문에서
         * i=1, j=3일 때와 i=3, j=1일때를 모두 sum에 더하기 때문에
         * 두 팀의 능력치 차이를 구할 때 aSum/2, bSum/2와 같이 2로 나누어서 계산해야 한다.
         */

        minGap = min(minGap, abs(aSum / 2 - bSum / 2));
        return;
    }

    for (int i = before + 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            back(cnt + 1, i);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    back(0, 0);
    cout << minGap;
}