[백준] 14889번 파이썬 _ 스타트와 링크

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

14889번: 스타트와 링크

문제유형 : 브루트포스

 

문제풀이 : 

• 조합을 이용한 완전탐색
  • nCn//2를 통해 팀을 반으로 나눌수있는 모든 경우를 구한다.
  • 각각의 경우에서 다시 n//2C2를 통해 2명씩 시너지를 구해서 팀의 능력치를 구한다.
  • 팀을 반으로 나눌수있는 모든 경우에 대해 팀의 능력치를 구했다면, 매칭되는 반대팀의 능력치와의 차이를 구해서 최소를 출력.
  • 매칭되는 팀은 조합을 모두 구한후에 반으로 나누고 뒤엣부분을 거꾸로 뒤집으면 순서대로 매칭되는 팀이된다.
  • ex(1,2,3 ~ 4,5,6) 각각의 팀 능력치를 구하고 두 차이를 빼준다. 

 

정답코드 :  

import sys
from itertools import combinations
input = sys.stdin.readline

n = int(input())
graph = []
team = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    team.append(i+1)

power = []

for i in combinations(team, n//2):
    # print(i)
    a = 0
    for j in combinations(i, 2):
        # print(j)
        # 1,2,3을 선택했을때 해당팀의 시너지
        a += graph[j[0]-1][j[1]-1]+graph[j[1]-1][j[0]-1]
    power.append(a)

end = len(power)//2
# 중간지점을 기점으로 팀이 나눠지기때문에 반반씩 나눠서 뒤에걸 거꾸로 뒤집으면 매칭되는 팀이 된다.
start_team = power[:end]
end_team = power[end:]
end_team = end_team[::-1]

answer = 100 # 최대차이
for i in range(end):
    answer = min(answer, abs(start_team[i]-end_team[i]))

print(answer)

근데 효율적이진 못한 코드같다. 시간이 오래걸림

더 시간을 줄일수있는 효율적인 코드가 있는지 생각해봐야겠다.