[Python] SW Expert Academy #4012 요리사

📚문제: #4012 요리사(모의 SW 역량테스트)

전체 코드

# 4012. 요리사

from itertools import combinations

# 함수
def min_diff(G, n, t):
    
    # 차이가 최소가 되는 값, 초기화
    min_val = int(1e10)
    
    # 재료 번호
    ing = [i for i in range(n)]
    
    # 조합을 만든다.
    ing_comb = list(combinations(ing, n // 2))
    
    # 조합을 절반으로 나눈다.
    ing_set_1 = ing_comb[:len(ing_comb) // 2]
    ing_set_2 = ing_comb[len(ing_comb)//2:]
    
    ing_set_2 = ing_set_2[::-1]
    
    for i in range(len(ing_set_1)):
        
        comb_1 = ing_set_1[i]
        comb_2 = ing_set_2[i]
        
        sum_val_1 = 0
        sum_val_2 = 0
        
        pair_1 = list(combinations(comb_1, 2))
        pair_2 = list(combinations(comb_2, 2))
        
        for pair in pair_1:
            
            i, j = pair
            
            sum_val_1 += (G[i][j]+G[j][i])
        
        for pair in pair_2:
            
            i, j =pair
            
            sum_val_2 += (G[i][j]+G[j][i])
        
        # 최소값 갱신
        min_val = min(min_val, abs(sum_val_1-sum_val_2))
    
    # 답안 출력
    print("#{} {}".format(t, min_val))
        
# 총 테스트 케이스의 개수 T
T = int(input())

# 테스트 케이스
for t in range(1, T+1):
    
    # 식재료의 수 N
    N = int(input())
    
    # S 초기화
    S = []
    
    # Sij가 주어진다.
    for _ in range(N):
        
        S.append(list(map(int, input().split())))
    
    # 함수 실행
    min_diff(S, N, t)