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

Problem

N명의 사람들을 N//2명으로 나누어 각 시너지의 합들을 더한 조합의 최솟값을 찾는 문제

Solution

1)combination을 통해 그룹 나누기
2)permutation을 통해 나눈 그룹의 조합들을 구해주기
3)나눈 그룹들의 시너지 합을 표에서 찾아 더해주기
4)최솟값을 구하기

Python Code

import sys
from itertools import combinations
from itertools import permutations
N=int(sys.stdin.readline())
NList=[i for i in range(1,N+1)]

arrList=[]

for _ in range(N):
    tmp=list(map(int,sys.stdin.readline().split()))
    arrList.append(tmp)
combiList=list(combinations(NList,N//2))

Asum=0
Bsum=0
minValue=1e9
def sumFunction(setRawPermu,setRemainPermu):
    global Asum
    global Bsum
    global minValue
    Asum=0
    Bsum=0


    for row in setRawPermu:

        Asum+=arrList[row[0]-1][row[1]-1]
    for row in setRemainPermu:
        Bsum+=arrList[row[0]-1][row[1]-1]
    minValue=min(minValue,abs(Asum-Bsum))

for combi in combiList:
    setRaw=list(combi)
    setRemain=list(set(NList)-set(setRaw))

    setRawPermu=list(permutations(setRaw,2))
    setRemainPermu=list(permutations(setRemain,2))
    sumFunction(setRawPermu,setRemainPermu)

print(minValue)