[Python] 14889번 : 스타트와 링크

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

14889번: 스타트와 링크

 

문제 3줄 요약

1. 짝수인 N명의 사람이 팀을 짜 축구를 한다.

2. 팀원들 간의 시너지가 존재한다. ex) 팀(1번 팀원 + 2번 팀원)의 능력치 = S12+ S21이다.

3. 팀 간 능력치의 차이가 최소가 되도록 팀을 짜봐라.

 

 

---

 

사람의 수인 N이 최대 20까지 이므로

브루트포스 알고리즘을 이용하였다.

 

최대 10 vs 10인 축구 경기가 될 것이다.

 

Step 1)

또한 경우의 수를 구하기 위해

조합 라이브러리인 combinations를 이용하였다.

 

Step 2)

팀원 간의 시너지는 두 명씩 존재하기에,

팀이 정해졌으면,

두 명씩 묶어 팀원간의 시너지를 더해 팀 능력치를 구해 비교한다.

 

Step 3)

스타트 팀과 링크 팀의 능력치 차이의 절댓값이

작은 경우를 갱신하여 최솟값을 찾는다.

 

 

from sys import stdin
from itertools import combinations

if __name__ == "__main__":
    N = int(stdin.readline())
    num_map, num_set, answer = [], set(), float('inf')

    for idx in range(1,N+1):
        num_map.append(list(map(int,stdin.readline().split())))
        num_set.add(idx)

	# Step 1) 팀 구성하기
    com_list = list(combinations(num_set,N//2))

    for idx in range(len(com_list)//2):
        start_score = 0
        
        # Step 2) 스타트팀 vs 링크팀
        for s in combinations(com_list[idx],2):
            start_score += num_map[s[0]-1][s[1]-1] + num_map[s[1]-1][s[0]-1]
        
        link_score = 0
        for l in combinations(num_set-set(com_list[idx]),2):
            link_score += num_map[l[0]-1][l[1]-1] + num_map[l[1]-1][l[0]-1]

        # Step 3) 능력치 차이의 최소 갱신
        min_gap = abs(start_score - link_score)
        if min_gap < answer:
            answer = min_gap
        if answer == 0:
            break
    
    print(answer)

 

축구 안한지 엄청 오래 된 것 같네

운동 좀 해야하는데..

여튼

 

끝!