(Python) 백준 14889번 : 스타트와 링크

 

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

14889번: 스타트와 링크

---

---

 

(Python) 백준 14889번 : 스타트와 링크¶

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

• 알고리즘 분류
  • 브루트 포스

---

In [1]:

from itertools import combinations
from collections import deque
import sys

In [2]:

## 팀의 능력치 합을 구한다.
def ability(x_team, S):
    n = len(x_team)
    sumv = 0
    for x in range(0,n-1):
        for y in range(x+1, n):
            sumv = sumv + S[x_team[x]][x_team[y]] + S[x_team[y]][x_team[x]]
    return sumv

In [3]:

if __name__ == '__main__':
    N = int(input()) ## 총 몇명?
    S = [list(map(int, input().split())) for _ in range(N)] ## 능력에대한 정보
    A = [int(i) for i in range(N)] ## 각 선수에게 0부터 N-1까지 숫자 부여
    team = deque(combinations(A,N//2))
    minv = sys.maxsize ##업데이트 해야 될 값.

    start_team = deque()
    link_team = deque()
    for _ in range(len(team)//2):
        start_team.append(team.popleft())
        link_team.append(team.pop())
    for i in range(len(start_team)):
        answerv = abs(ability(start_team[i],S) - ability(link_team[i],S))
        if answerv < minv:
            minv = answerv
    print(minv)

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0
2