Algorithm Problems

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

WakaraNai 2021. 5. 19. 00:55
728x90
반응형

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

 

Python

from itertools import combinations
import sys

n = int(sys.stdin.readline().rstrip())
arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))


combi = list(combinations([i for i in range(1,n+1)],n//2))
#print(combi)


result = 100000000
team = [ list(combinations(combi[i],2)) for i in range(len(combi))]
for i in range(len(team)):
    #print(x)
    start = team[i]
    link = team[-i-1]

    ssum = 0
    for s in start:
        ssum+= arr[s[0]-1][s[1]-1] + arr[s[1]-1][s[0]-1]
    lsum = 0
    for s in link:
        lsum+= arr[s[0]-1][s[1]-1] + arr[s[1]-1][s[0]-1]
    
    result = min(result, abs(ssum-lsum))
    
    
print(result)
728x90
반응형