[백준/14889/파이썬] 스타트와 링크

---

소스코드

from itertools import combinations

N = int(input())

startlink = [list(map(int, input().split())) for _ in range(N)]

answer = int(1e9)

num = [i for i in range(N)]

team = list(combinations(num,N//2))

for start_player in team:

  start_total = 0

  link_total = 0

  link_player = list(set(num)-set(start_player))

  for i,j in list(combinations(start_player,2)):

    start_total += startlink[i][j]

    start_total += startlink[j][i]

  for i,j in list(combinations(link_player,2)):

    link_total += startlink[i][j]

    link_total += startlink[j][i]   

  answer = min(answer, abs(start_total - link_total))

print(answer) 

---

알고리즘

1. 가능한 팀원의 조합을 itertools의 combinations를 이용해서 구합니다.

ex) [(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 2, 3), (0, 2, 4), (0, 2, 5), (0, 3, 4), (0, 3, 5), (0, 4, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

2. 팀원들의 조합을 가지고 각각 start 팀과 link 팀의 총 합계를 구합니다.

3. 반복문을 돌 때마다 answer을 갱신해나가며 가장 작은 값을 출력합니다.