스타트와 링크

백준 14889

조합을 itertools 쓰지 않고 직접 구현해서 해결해보기. 시간 초과에 주의하기

#1~n을 둘로 나누는 모든 조합을 구해서
#각각 sij의 합을 구해 그 차이를 계산.
#그 차이의 최솟값 갱신. 가장 최솟값 출력


def combinations(arr, r): # 배열 arr 중 r개를 뽑는 조합.
    result = []

    if r == 0:
        return [[]]

    for i in range(len(arr)):
        p = arr[i]
        for ele in combinations(arr[i+1:], r-1):
            result.append([p] + ele)
    
    return result



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

nums = [x for x in range(1, n+1)]
comb = list(combinations(nums, n//2)) 


ans = 1e9
for k in range(len(comb)//2):
    teamA = comb[k]
    teamB = comb[len(comb)-k-1]
    
    sum1, sum2 = 0, 0

    for i in range(n//2):
        for j in range(i, n//2):
            sum1 += sij[teamA[i]-1][teamA[j]-1] + sij[teamA[j]-1][teamA[i]-1]
            sum2 += sij[teamB[i]-1][teamB[j]-1] + sij[teamB[j]-1][teamB[i]-1]
    
    if abs(sum1-sum2) < ans:
        ans = abs(sum1-sum2)

print(ans)
    

팀을 할 수 있는 모든 조합 = comb.
반복문 조건을 줄이기 위해 comb의 절반만 보고, 해당 팀의 반대 팀을 따져서
각각 능력치를 계산한다.