[SWEA] 4012. [모의 SW 역량테스트] 요리사 (211012)

소감

• [업데이트] 변수명 구체적으로 변경 : food_combination -> ingredient_combination
• 문제가 구체적이지 않아서 애를 먹었다. 디버깅과 문제의 문제점..! 을 짚어준 댓글이 없었다면 풀기 힘들었을 것 같다.
• 재료 2개를 구할 경우 (1, 2) (2, 1) 조합으로 풀면 되는데 재료가 3개일 경우 2개를 선택하는 건지, 아니면 재료 3개를 모두 선택하는건지 등에 대한 정보가 없었다.
• 이차원 리스트 벽 세우는걸 좀 더 깔끔하게 구현할 수 없을까..?

접근법

• 이차원리스트를 받아온다. 이 때 재료와 인덱스 순서를 맞추기 위해 좌측, 상단에 벽을 세운다.
• 전체 리스트에서 조합으로 2개 선택한다.
• 반복문을 돌며 음식별 맛의 합계를 구한다.
• 이 때, 재료를 순열로 다시 구해서 음식1과 음식2의 맛을 구하고 그 차이가 최소라면 최솟값으로 대체한다.
• 매 조합마다 음식의 맛을 리셋한다.

6
0 37 26 52 77 20
32 0 15 26 75 16
54 33 0 79 37 90
92 10 66 0 92 3
64 7 89 89 0 21
80 49 94 68 5 0

재료가 6개이고 재료 3개씩(N//2)을 사용해서 두 개의 음식을 만든다고 해보자.

이때 음식을 구하는 모든 조합은 list [1, 2, 3, 4, 5, 6] 에서 3개를 선택하면 된다.

모두 20개의 조합이 나온다.

ingredient_combination = [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (1, 5, 6), (2, 3, 4), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)]

(1, 2, 3) 재료를 사용한 음식이 있다면, 남은 재료는 (4, 5, 6)일 것이다.

음식 A를 위해 식재료 (1, 2, 3) 이 사용되었다면 A의 맛은 S[1][2] + S[2][1] + S[2][3] + S[3][2] + S[1][3] + S[3][1] 이 된다.

따라서 (1, 2, 3) 에서 2개를 선택하는 순열을 구한다.

select_two_A = [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

음식 A의 맛을 구하기 위해 처음 받아온 N+1 * N+1 보드에서 해당 맛의 좌표를 찾아 값을 더한다.

for k in range(len(select_two_A)):                             
	foodA += board[select_two_A[k][0]][select_two_A[k][1]]

음식 B도 같은 방법으로 구하고, A와 B 값의 차이의 절대값을 구한다.

 

그 다음 food_combination 조합을 반복한다.

(1, 2, 4) 와 (3, 5, 6)...

총 20//2 = 10개의 반복이 이루어진다.

최종코드

import sys                                                                                                                
sys.stdin = open('input.txt')                                                                                             
from itertools import combinations, permutations                                                                          
                                                                                                                          
def min_difference(N, board):                                                                                             
    # 가능한 재료 조합을 찾는다.                                                                                                     
    ingredient_list = [x+1 for x in range(N)]                                                                             
    ingredient_combination = list(combinations(ingredient_list, N//2))                                                    
    min_difference = 999999                                                                                               
                                                                                                                          
                                                                                                                          
    # 반복문을 돌며 맛의 합계를 구하고 그 최솟값을 업데이트한다.                                                                                   
    for i in range(len(ingredient_combination)//2):                                                                       
        # 음식의 맛을 설정한다.                                                                                                    
        foodA = 0                                                                                                         
        foodB = 0                                                                                                         
                                                                                                                          
        # 재료 조합을 만든다. ex. (1, 2, 3) 으로 만드는 순열 (1, 2)(2, 1)(1, 3)(3, 1)(2, 3)(3, 2)                                        
        select_two_A = list(permutations(ingredient_combination[i], 2))                                                   
        select_two_B = list(permutations(ingredient_combination[len(ingredient_combination)-i-1], 2))                     
                                                                                                                          
        # 각 요리별로 맛을 구한다.                                                                                                  
        for k in range(len(select_two_A)):                                                                                
            foodA += board[select_two_A[k][0]][select_two_A[k][1]]                                                        
        for l in range(len(select_two_B)):                                                                                
            foodB += board[select_two_B[l][0]][select_two_B[l][1]]                                                        
                                                                                                                          
        # 요리 A와 B의 차이를 구한다.                                                                                               
        difference = abs(foodA-foodB)                                                                                     
                                                                                                                          
        # 차이가 최솟값이라면 업데이트한다.                                                                                              
        if min_difference > difference:                                                                                   
            min_difference = difference                                                                                   
                                                                                                                          
    # 가장 차이가 적은 결과를 리턴한다.                                                                                                 
    return min_difference                                                                                                 
                                                                                                                          
                                                                                                                          
T = int(input())                                                                                                          
                                                                                                                          
                                                                                                                          
for tc in range(1, T + 1):                                                                                                
    N = int(input())  # 식재료 수                                                                                             
    board = [[0] * (N+1)] + [([0]+list(map(int, input().split()))) for _ in range(N)]  # 이차원 리스트 좌/상 벽 세움                 
    print("#{} {}".format(tc, min_difference(N, board)))

 

추가코드

DFS 를 사용하는 방법

출처 : 서울3반

from itertools import combinations
def total(items):
    result = 0
    for a, b in list(combinations(items, 2)):
        result += sng[a][b] + sng[b][a]
    return result

def dfs(idx, where):
    global answer
    if idx == N // 2:
        A = []
        B = []
        for i in range(N):
            if visited[i]:
                A.append(i)
            else:
                B.append(i)
        result = abs(total(A) - total(B))
        answer = min(result, answer)
        return

    for i in range(where, N):
        if visited[i] == 0:
            visited[i] = 1
            dfs(idx+1, i+1)
            visited[i] = 0

for tc in range(1, int(input()) + 1):
    N = int(input())
    sng = [list(map(int, input().split())) for _ in range(N)]
    answer = 1e9
    visited = [0] * N
    dfs(0, 0)
    print(f'#{tc} {answer}')