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

문제

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

---

문제 요약

n명의 사람을 절반으로 나누어 스타트 팀과 링크 팀을 만든다.

 

S[i][j]는 i번 사람과 j번 사람이 같은 팀에 속해 있을 때, 팀에 더해지는 능력치이다.

(S[i][j]와 S[j][i]는 다를 수 있다.)

 

n과 S[i][j]가 모두 주어졌을 때, 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력한다.

---

코드

#include <iostream>
#include <algorithm>

#define MAX_N 20

using namespace std;

int n;
int S[MAX_N][MAX_N];

// 최소 차이
int res = 1e9;

// i번 사람이 선택 되었는지
bool selected[MAX_N];

// 각 팀의 능력치 계산 후 차이의 최솟값을 갱신하는 함수
void update() {
    int sum_a = 0;
    int sum_b = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (selected[i] && selected[j]) {
                sum_a += S[i][j];
            }
            else if (!selected[i] && !selected[j]) {
                sum_b += S[i][j];
            }
        }
    }

    int diff = abs(sum_a - sum_b);

    res = min(res, diff);

}

// 현재 cnt명으로 팀을 구성했고, idx번부터 팀으로 포함시키는 경우를 탐색하는 함수
void dfs(int cnt, int idx) {
    // 팀원을 모두 고른 경우
    if (cnt == n / 2) {
        update(); // 능력치 계산
        return;
    }

    // 가능한 범위에서 다음 사람을 골라 팀을 꾸려보기
    for (int i = idx; i < n; i++) {
        selected[i] = true;
        dfs(cnt + 1, i + 1);
        selected[i] = false;
    }
}

int main() {
    // 입력
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> S[i][j];
        }
    }

    // 완전탐색(백트래킹)을 통해 팀을 만들 수 있는 모든 경우의 수 탐색
    dfs(0, 0);

    // 출력
    cout << res;

    return 0;
}

---

코드 설명

1. n과 S[i][j]를 입력 받는다.

 

2.  함수 dfs를 선언하고, 팀이 가능한 모든 경우의 수를 완전탐색(백트래킹)한다.

+ 한 팀만 결정하면, 다른 팀은 자동으로 구성된다.

 

2 - 1. 팀원을 모두 고른 경우, 그 때 두 팀의 능력치를 계산하여 비교하고, 차이를 갱신한다.

 

2 - 2. 팀원을 더 골라야 하는 경우, 다음 번호 사람들을 골라 팀이 가능한지 재귀적으로 탐색한다.

 

3. 최소 차이를 출력한다.

---

고찰

오랜만에 백트래킹을 구현했더니, 생각보다 잘 되지 않았다.

 

좀 더 많은 연습이 필요하다!!