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

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=%EC%9A%94%EB%A6%AC%EC%82%AC&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

🔥 작성 코드

# 두 손님의 맛 차이 계산
def sol(lst1, lst2):
    global result

    # 첫 손님의 음식 맛
    tot1 = 0
    for i in lst1:
        for j in lst1:
            if i != j:
                tot1 += S[i][j]

    # 다음 손님의 음식 맛
    tot2 = 0
    for i in lst2:
        for j in lst2:
            if i != j:
                tot2 += S[i][j]

    # 결과값 갱신
    if result > abs(tot1-tot2):
        result = abs(tot1-tot2)
    return


# 두 명의 손님에게 제공할 음식 명단 고르기
def food(lst, idx):
    lst0 = [x for x in lst]

    # 한 손님에게 제공할 음식이 전체 음식의 절반일 때
    # 다른 손님에게 제공할 음식 명단을 만들고 sol함수로 보냄
    if len(lst0) == N//2:
        lst1 = [x for x in lst]
        lst2 = []
        for i in range(N):
            if f[i] not in lst1:
                lst2.append(f[i])
        sol(lst1, lst2)

    elif idx >= N:
        return

    else:
        food(lst0, idx+1)
        lst0.append(f[idx])
        food(lst0, idx+1)
    return


T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    S = [list(map(int, input().split())) for _ in range(N)]

    # 음식의 종류
    f = [i for i in range(N)]

    # 첫 손님에게 0번 음식 고정
    lst = [0]
    result = 20000
    food(lst, 1)

    print(f'#{test_case} {result}')

 

 

⭕ 해설

1.  두 손님에게 줄 음식 명단을 만들었습니다.
2.  차이의 최솟값을 구하는 것이므로 두 손님의 음식 조합이 겹치는 경우는 제외해도 됩니다.
   • ex)  N=4 일 때, 음식은 f = [0, 1, 2, 3]
   • 1번 손님 : [0, 1],  2번 손님 : [2, 3]
   • 1번 손님 : [2, 3],  2번 손님 : [0, 1]
   • 이 두 경우는 같습니다.
3.  따라서 1번 손님의 음식 명단에 0번 음식을 고정시켜주어 중복되는 경우를 모두 제외해 줍니다.
4.  1번 손님의 음식을 N//2 개 까지 채운다면 2번 손님의 음식을 채워줍니다.
5.  모든 조합에서 맛 차이를 계산해주며 결과값을 갱신합니다.