Python으로 푸는 SW Expert Academy 4012. 요리사

SW Expert 아카데미 4012. 요리사

 문제는 입력 받는 방법의 차이는 있으나,

백준의 스타트와 링크 문제와 같은 문제이다.

두 명의 손님에게 두 개의 요리를 만들어 제공하려고 한다.

두 명의 손님은 식성이 비슷하기 때문에, 최대한 비슷한 맛의 음식을 만들어 내야 한다.

식재료의 종류를 둘로 나누지만, 비슷한 맛의 음식을 두 가지 만들어 제공하기로 했을 때

각각 음식에 사용할 식재료들의 궁합에 따라 시너지의 합을 구하고

그 시너지의 합의 차가 최소가 되는 경우를 찾아

그 최솟값을 정답으로 출력하도록 코드를 짜도록 하자.

문제 보러 가기

백준 스타트와 링크 풀이 보기

github에서 코드 보기

문제에서 제시한 조건

- 두 명의 손님은 식성이 비슷하여 최대한 비슷한 맛의 음식을 만들어 내야 한다.

- N 개의 식재료가 있고 식재료들을 반으로 분류하여 두 개의 요리를 하려고 한다. (N은 항상 짝수다)

비슷한 맛의 음식을 만들기 위해서는 두 음식 각각 맛의 차이가 최소가 되도록 재료를 분배해야 한다.

문제 풀이 방법

각 음식별로 사용할 재료들을 반으로 분류하고 각각의 요리별로 재료들의 시너지값을 구한 후, 요리별 시너지 값의 차가 가장 적은 수를 반환한다.

파이썬 코드

import itertools
 
def cal(lines, a, b):
    return lines[int(a)][int(b)]
 
def bruteforce(lines, n):
    count = n // 2
    incredients = range(n)
    combis = itertools.combinations(incredients, count)
    incredients = set(incredients)
    min_result = 9999999
 
    for combi in combis:
        afood = set(list(combi))
        bfood = list(incredients - afood)
        afood_total = 0
        bfood_total = 0
 
        # 조합에 0이 포함되어 있지 않는 부분이 딱 중간 부분임
        # (0이 포함되거나, 포함되지 않거나로 반을 나눈다)
        if combi[0] != 0:
            break
 
        afood = list(afood)
        # itertools는 제네레이터 객체로 반환하여 값들을 yield해 준다.
        afood_combi = itertools.combinations(afood, 2)
        for coma in afood_combi:
            afood_total += cal(lines, coma[0], coma[1])
 
        bfood_combi = itertools.combinations(bfood, 2)
        for comb in bfood_combi:
            bfood_total += cal(lines, comb[0], comb[1])
 
        if abs(afood_total - bfood_total) < min_result:
            min_result = abs(afood_total - bfood_total)
 
    return min_result
 
 
if __name__ == "__main__":
    c = int(input().strip())
    for t in range(c):
        n = int(input().strip())
        lines = []
        for i in range(n):
            line = list(map(int, input().strip().split()))
            lines.append(line)
 
        # a,b의 값이 정해졌을 때 a-b, b-a의 시너지를 한번만 조회할 수 있도록, 값들을 한곳에 모아둔다
        for i in range(n):
            for j in range(n):
                if j > i:
                    lines[i][j] = lines[i][j] + lines[j][i]
                    lines[j][i] = 0
        print('#{0} {1}'.format(t + 1, bruteforce(lines,n)))

#삼성 모의 SW 역량테스트 #python 요리사 #4012 요리사 #python 4012 요리사 #파이썬으로 푸는 #파이썬 삼성 풀이 #삼성 코딩 테스트 요리사 #4012 요리사 python #파이썬 4012 요리사 #4012 요리사 파이썬