[BOJ] 14889 스타트와 링크 - Python

문제

---

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

14889번: 스타트와 링크

풀이

---

문제의 상황, 주어지는 입력의 크기, 제한 시간을 모두 고려해보면 완전 탐색을 이용하여 문제 풀이가 가능함을 알 수 있습니다.

따라서 아래와 같은 로직으로 간단하게 문제를 풀이할 수 있습니다.

1. combination을 사용하여 사람들을 두 팀으로 나눈다.
2. 두 팀에 대한 점수를 각각 구하고 점수 차이가 현재 답보다 작을 시 갱신한다.

 

풀이 코드는 아래와 같습니다.

from itertools import combinations as C

N = int(input())
answer = 987654321
people = [i for i in range(N)]
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
        
# 팀 뽑기
for team1 in list(C(people, N // 2)):
    team2 = [i for i in people if i not in team1]
        
    # 팀 별 점수 구하기
    score1 = 0
    score2 = 0
    for i in range(N // 2):
        for j in range(i + 1, N // 2):
            score1 += graph[team1[i]][team1[j]] + graph[team1[j]][team1[i]]
            score2 += graph[team2[i]][team2[j]] + graphx[team2[j]][team2[i]]
    answer = min(abs(score1 - score2) , answer)
    
print(answer)