[백준 14889] 스타트와 링크 with Python

문제 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

풀이

import sys
import itertools

N = int(sys.stdin.readline())
skill = [[x for x in map(int, sys.stdin.readline().split())] for _ in range(N)]
comb = map(set, itertools.combinations([x for x in range(N)], N//2))
min_diff = 100*(N-1)*2

for team in comb:
    if 0 in team:
        op = set(range(N)) - team
        team_skill = 0
        op_skill = 0
        for j in team:
            for k in team:
                team_skill += skill[j][k]
        for j in op:
            for k in op:
                op_skill += skill[j][k]
        min_diff = min(min_diff, abs(team_skill-op_skill))

print(min_diff)

itertools.combinations를 활용해서 N/2 명의 사람을 뽑는 모든 경우의 수를 comb에 저장한다.

 

이 때, 뽑힌 N/2명의 사람은 team에 속하고 그 나머지는 자동으로 상대방 편인 op에 속하게 된다. 

 

team과 op의 능력치 합의 차이를 구하여 최솟값을 계속 갱신한다.

 

이 때, for문 바로 밑에 "if 0 in team:"의 의미는 중복을 제거하기 위함이다. 예를 들어 4명의 사람이 있을 때, team에 [1번, 2번], op에 [3번, 4번]이 뽑힌 경우와, team에 [3번, 4번], op에 [1번, 2번]이 뽑힌 경우는 능력치의 차를 구하는데 있어 완전히 같은 경우이다. 따라서, 특정 한 사람(여기서는 0)이 team에 계속 뽑힌다고 가정하면 이러한 중복을 완전히 피할 수 있다.