백준 스타트와 링크 14889 완전탐색

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

14889번: 스타트와 링크

 

• 두 팀으로 나누는 조합 생성(p)
• 각각의 팀이 가지는 능력치 담은 power 배열 0으로 초기화
• 각 팀마다 2명씩 뽑아서 2명의 팀원의 능력치를 해당 power 배열에 담음
• 팀은 결국 두 팀만 만들어지므로 power배열의 끝에서부터 안쪽으로 상대팀과의 능력 차 구해주면 됨
• result에 능력 차이 값을 담고, 마지막에 min(result)로 정답 출력

 

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

result = []
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

nums = [i for i in range(0,n)]

p = list(combinations(nums, int(n/2)))
power = [0] * len(p)
for i in range(len(p)):
    p_list = list(combinations(p[i], 2))
    for j in p_list:
        x, y = j
        power[i] += graph[x][y] + graph[y][x]

for i in range(int(len(power)/2)):
    j = len(power)-i-1
    result.append(abs(power[i]-power[j]))

print(min(result))