[백준 14889번] 스타트와 링크 - Python으로 구현하기

[백준 14889번] 스타트와 링크 - Python으로 구현하기

 

문제 접근

• 두 팀으로 나누는 경우의 수를 어떻게 구할지?
• itertools 의 combinations 모듈 사용! n//2 개의 조합을 뽑아서 1팀과 2팀으로 나눔

 

생각해볼 점

• combinations 모듈 없이 어떻게 구현할지?

from itertools import combinations as cm
import math

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

min_ans=math.inf	# 정답

for case in cm(range(1,n+1),n//2):	# 두 팀으로 나눌 수 있는 경우의 수
    s1 = s2 = 0
    
    for i in case:	# 1팀 점수
        for j in case:
            s1+=datas[i-1][j-1]

    res = set(range(1, n + 1)) - set(case)	# 2팀 점수
    for i in res:
        for j in res:
            s2+=datas[i-1][j-1]
    min_ans=min(min_ans,abs(s1-s2))
print(min_ans)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!