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

1. 문제 링크

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

14889번: 스타트와 링크

 

2. 문제 요약

• 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력

 

3. 아이디어 정리

1. 조합을 이용하여 2개의 팀으로 나눈다.
2. 각 팀의 능력치를 구한다.
3. 각 팀의 능력치 합의 차를 구한 뒤 갱신한다.

 

4. 문제 풀이

4-1. 내 풀이

"""
    return : 스타트 팀과 링크 팀의 능력치 차이 최솟값
"""
import sys
from itertools import combinations

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = int(1e9)  # 최솟값

for comb in combinations(range(0, n), n // 2):
    a_team = list(comb)
    b_team = [i for i in range(0, n) if i not in a_team]

    a_score = 0
    b_score = 0

    for i in range(0, len(a_team) - 1):
        for j in range(i + 1, len(a_team)):
            a_score += graph[a_team[i]][a_team[j]] + graph[a_team[j]][a_team[i]]
            b_score += graph[b_team[i]][b_team[j]] + graph[b_team[j]][b_team[i]]

    result = min(result, abs(a_score - b_score))

print(result)

 

 

5. 결론

• 구현 문제