[백준 14889번] 스타트와 링크(재풀이)

 

14889번: 스타트와 링크

 

 

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

from itertools import combinations
from itertools import permutations

n = int(input())

member = set([x for x in range(n)])

answer = float("inf")

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

case_list = list(combinations([x for x in range(n)], n//2))
case_list = case_list[:len(case_list)//2]

def calculate(numbers):
    cases = permutations(numbers,2)
    return sum([area[x][y] for x,y in cases])

for team_a in case_list:
    team_b = [x for x in range(n) if x not in team_a]
    diff = abs(calculate(team_a)-calculate(team_b))

    if diff < answer:
        answer = diff

print(answer)

 

본 문제는 이전에 포스팅했던 문제 중 하나인데, N명의 팀을 2개의 팀으로 나누었을 때 각 팀의 능력치의 차이를 최소화하는 문제이다.

 

이전에는 DFS를 사용하여 엄청 복잡하게 풀기도 했고 시간이 오래걸렸었는데, 이번에는 순열과 조합을 활용하여 경우의 수를 모두 구해주는 방식으로 간단하게 풀이할 수 있었다.

 

이전에 비해 완전 탐색(Brute Force)에 대한 감이 생긴 것 같아서 뿌듯했던 문제였다 :)