[백준] 14889 스타트와 링크 (파이썬 python)

 

 

문제 링크

 

 

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

14889번: 스타트와 링크

 

 

문제

 

 

 

 

 

문제 풀이

 

 

from itertools import combinations
n = int(input())
nums = [i for i in range(n)]
result = 1e9
s = []
for _ in range(n):
    s.append(list(map(int, input().split())))

for start in combinations(nums, n//2):
    link = list(set(nums) - set(start))
    startSum, linkSum = 0, 0
    for numStart in combinations(start, 2):
        startSum += s[numStart[0]][numStart[1]]
        startSum += s[numStart[1]][numStart[0]]
    for numLink in combinations(link, 2):
        linkSum += s[numLink[0]][numLink[1]]
        linkSum += s[numLink[1]][numLink[0]]
    result = min(result, abs(startSum - linkSum))

print(result)

 

 

itertools 모듈의 combinations 조합 함수를 이용해서 팀의 구성 조합을 만들어준다!

combinations(nums, n//2)를 통해 start 팀의 가능한 조합들에 대해 모두 검사를 해준다.

이 때, nums는 선수 번호 리스트이다.

link에 nums에서 start의 set을 빼주어 현재 검사 중인 start 팀원 제외 팀원들을 넣어준다.

이제 start 안에 있는 팀원들, link 안에 있는 팀원들을

두 명씩 또 다시 조합으로 뽑아서 전체 모두 팀sum에 능력치들을 더해준다.

능력치를 더하는 과정이 끝나면 min을 통해 최소값인지 판정하고

다시 다음 조합으로 넘어간다.