4012. [모의 SW 역량테스트] 요리사

출처 : SW Expert Academy

문제

식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고, 가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때, 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.

[입력]

T : 총 테스트 케이스의 개수
N : 식재료의 수

다음 N개의 줄에는 N * N개의 시너지 Sij값들이 주어진다.

[출력]
#과 두 음식 간의 맛의 차이가 최소가 되도록 A음식과 B음식을 만들었을 때 그 차이 값

코드

# pass!

import sys
sys.stdin = open('input.txt')

def food (first , second):
    global min_sub
    a = 0
    b = 0
    # 재료 갯수만큼 반복 더함
    for i in range(len(first)):
        # Sij + Sji 부분
        a += (arr[first[i][0]][first[i][1]] + arr[first[i][1]][first[i][0]])
        b += (arr[second[i][0]][second[i][1]] + arr[second[i][1]][second[i][0]])

    if min_sub > abs(a-b):
        min_sub = abs(a-b)

# 조합1 = 총 재료를 반으로 나누는 조합
def com(n, r, s, k):

    if k == r:
        comb_list.append(comb[:])
        return

    else:
        for i in range(s, n-r+k+1):
            comb[k] = i
            com(n, r, i+1, k+1)

# 조합2 = 한사람의 재료를 2개씩 조합 ex)[0,1,2] -> [[0,1],[0,2],[1,2]]
def comb2(arr):
    result = []
    for i in range(len(arr)):
        for j in arr[i + 1:]:
            result.append((arr[i], j))
    return result

T = int(input())

for tc in range(1,T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    comb = [0] * (N//2)
    min_sub = 999999
    comb_list=[]

    com(N, N//2, 0, 0)

    first = comb_list[:len(comb_list)//2]
    second = comb_list[:len(comb_list)//2-1:-1]


    for i in range(len(first)):
        food(comb2(first[i]), comb2(second[i]))

    print("#{} {}".format(tc, min_sub))

풀이

1. 주어진 식재료 수 N개중 N//2개 조합 만들기
2. comb_list는 N//2개짜리 모든 조합이 들어있다.
   comb_list에 6개가 들어있다고 하면,
   0번째 리스트와 5번째 리스트가 한 세트를 이룬다.
   ex) [0,1,2,3,4,5] -> [0,1,2]/[3,4,5]
   그러므로 comb_list의 반은 first, 남은 반의 역순을 second로 정의
3. first, second 리스트에서 2개씩 조합을 구한다. => comb2함수
   시너지 정보(Sij)를 얻기 위함
4. 시너지 정보 값을 모두 합하여 최소 차이값을 구한다. => food함수

장애물

1. 조합 함수 만드는 거 자체가 장애물이였다. ㅎㅎ 더 연습합시다!
2. 처음 문제를 무조건 2개씩의 재료만으로 만드는 줄 알고 풀어서 실패.
   -> 각 재료의 갯수는 N//2개씩!!
3. first와 second가 한 세트라는 건 알고 시작했지만
   중간에 second는 역순으로 가져가야 한다는 사실을 뒤늦게 깨달았다.
4. list 복사!!!!!
   이거 진짜 주의!!!

   comb_list.append(comb) ------<1>
   comb_list.append(comb[:])----<2>
    

처음 <1>로 작성했었는데 결과가 예를 들어,
[0,1,2,3,4,5]의 3개의 조합을 구하는 comb1에서
[[3,4,5],[3,4,5] ...[3,4,5]]로 나온다.
이게 comb를 append 하는건데 함수가 진행될때마다 comb는 바뀌고
저장되어있는 메모리위치의 값을 저장하는 거라서
마지막 저장인 [3,4,5]가 최종적으로 나오게 된다

이거 해결하려면
슬라이싱!!
<2>처럼 작성해야 한다!!