[백준 14889] 스타트와 링크

1. 문제

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

2. 접근 방법

두 팀으로 나누고 각각의 능력치를 더해주면 됩니다.

두 팀이라 불리언 값을 사용해서 팀을 나눴습니다.

(참고: rebas.kr/754)

 

괜히 어렵게 생각했다가 슬펐던 문제 ^-^

3. 코드

python

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 team[i] and team[j]:
                    s1 += scores[i][j]
                if not team[i] and not team[j]:
                    s2 += scores[i][j]
        ans = min(ans, abs(s1-s2))
        return
    team[idx] = True
    solve(cnt+1, idx+1)
    team[idx] = False
    solve(cnt, idx+1)

N = int(input())
scores = [list(map(int, input().split())) for _ in range(N)]
team = [False]*N
ans = 1e9

solve(0, 0)
print(ans)

4. 마치며

마치며~!