BOJ 14889 · 스타트와 링크

알고리즘 분류 : 브루트 포스  

두 팀으로 나눠서 두 팀의 능력치 차에 대한 최솟값을 구하는 문제다. 재귀 함수를 이용하여 구현할 수 있다.

• 재귀 함수는 두 팀으로 나누는 과정에 이용한다.
• 팀을 구분하는 체크 배열 c를 둔다. 팀의 구분은 true와 false로 한다.
• 재귀 함수 종료 조건은 인덱스가 N을 벗어났을 때이거나 팀 인원이 N/2 명이 되었을 때이다.
• 팀 능력치의 총합은 N^2 for 문으로 구한다.
• Aij 는 i와 j가 같은 팀일 때의 능력치이며, Aij와 Aji는 값이 다를 수 있으므로 둘 다 더해야 한다.
• 스타트 팀은 c[i] == true AND c[j] == true 이며, 링크 팀은 c[i] == false AND c[j] == false 이다.

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n, ans = 1e9;
int a[20][20];
bool c[20];

void solve(int cnt, int idx) {
    if (idx == n) return;
    if (cnt == n/2) {
        int s1 = 0, s2 = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (c[i] && c[j]) s1 += a[i][j];
                if (!c[i] && !c[j]) s2 += a[i][j];
            }
        }
        ans = min(ans, abs(s1-s2));
        return;
    }
    c[idx] = true;
    solve(cnt+1, idx+1);
    c[idx] = false;
    solve(cnt, idx+1);
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

import sys
n = int(sys.stdin.readline())
a = [list(map(int, input().split())) for _ in range(n)]
c = [False]*n
ans = 1e9

def solve(cnt, idx):
    global ans
    if idx == n:
        return
    if cnt == n//2:
        s1, s2 = 0, 0
        for i in range(n):
            for j in range(n):
                if c[i] and c[j]:
                    s1 += a[i][j]
                if not c[i] and not c[j]:
                    s2 += a[i][j]
        ans = min(ans, abs(s1-s2))
        return
    c[idx] = True
    solve(cnt+1, idx+1)
    c[idx] = False
    solve(cnt, idx+1)

solve(0, 0)
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 14889