백준 14889 스타트와 링크 - 파이썬

 

풀이.

파이썬의 내장 라이브러리 itertools의 combinaition으로 조합을 구하여서

쉽게 해결할 수 있다. 또한 주의 하여야할 점이 팀에 구성멤버가 3명이상 넘어가면 각각의 멤버들의 조합에 대한 능력치들을 모두 구하여서 더해주어야한다.

 

소스코드.

import sys
import itertools

def calc(comb, stats):
    # start팀과 link 팀 나누기
    start = comb[0:len(comb)//2]
    link = comb[len(comb)//2:]
    link.reverse()
    result = 10000
    for s, l in zip(start, link):
        sc = itertools.combinations(s, 2)
        lc = itertools.combinations(l, 2)
        s_score = 0
        l_score = 0
        for i, j in zip(sc, lc):
            s_score += stats[i[0]][i[1]] + stats[i[1]][i[0]]
            l_score += stats[j[0]][j[1]] + stats[j[1]][j[0]]
        score = abs(s_score - l_score)
        if score == 0:
            return 0
        elif score < result:
            result = score
    return result


N = int(sys.stdin.readline())
com = [i for i in range(N)] # 0~N까지 요소를 가지는 리스트 생성

stats = [] # 능력치를 저장할 리스트
for i in range(N):
    # 능력치 입력받기
    s = list(map(int, sys.stdin.readline().split()))
    stats.append(s)

comb = itertools.combinations(com, N//2) # N//2의 조합 생성
print(calc(list(comb), stats))