[백준/삼성기출] 14889 스타트와 링크 - 완전탐색과 combinations

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

14889번: 스타트와 링크

 

완전탐색으로 풀었다 ! 

파이썬에 조합 라이브러리 combinations가 있는데, 조합 라이브러리를 완전 탐색에 유용하게 쓸 수 있었다. 

N 명중 N//2를 뽑는 조합을 구했고 뽑은 N//2 명의 팀원들은 start 팀이라고 한다. 

그리고 start 팀에 들어가지 않는 팀원들은 link 팀에 속하게 되는데, 이를 집합 set() 화 시켜서 차집합으로 구했다 ! 

그러면 현재 총 6명이 있었다고 치면, start = (1,2,3) link = (4,5,6) 와 같은 예가 나올것이다. 

그런데 우리는 Sij와 Sji를 더한 능력치의 합을 구해야 한다는 것 !!

그러므로 start = (1,2,3)내에서도 array[1][2] + array[2][1] , array[2][3] + array[3][2], array[1][3] + array[3][1] 

을 더해주어야 하는데 이 과정도 combination(start,2) 로 모든 경우를 확인할 수 있다 

# 14889 스타트와 링크
from itertools import combinations

n = int(input())
numbers = [i for i in range(n)]
array = []

for i in range(n):
    array.append(list(map(int, input().split())))

cases = combinations(numbers, n//2)
result = int(1e9)

for case in cases:
    check_start = combinations(case, 2)
    outofcase = list(set(numbers) - set(case))
    check_link = combinations(outofcase, 2)
    start, link = 0, 0
    for i in check_start:
        start += array[i[0]][i[1]] + array[i[1]][i[0]]
    for i in check_link:
        link += array[i[0]][i[1]] + array[i[1]][i[0]]
    result = min(result, abs(start-link))


print(result)