[Python] 백준 2961 도영이가 만든 맛있는 음식

 

문제 분석

• 재료 n개
• 각 재료의 신맛 S, 쓴맛 B
• 신맛 : 사용한 재료의 신맛의 곱
• 쓴맛 : 사용한 재료의 쓴맛의 곱
• 적어도 하나의 재료 사용
• 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램

 

코드 설계

• 재료가 총 n개 주어졌을 때
• 1~n개의 재료를 뽑고 그때의 신맛과 쓴맛을 구한뒤, 최소 차 구하기
• 뽑을 때는 중복 x, 순서 x : 조합 Combinations

 

정답 코드

import sys
input = sys.stdin.readline
from itertools import combinations

n = int(input())
taste = [list(map(int, input().split())) for _ in range(n)]

min_gap = float('inf')
for i in range(1, n+1) : # 1~n개까지 -> i
    for com in combinations(taste, i) : # 여러 재료 중 i개 선택
        sour = 1
        bitter = 0
        for k in range(len(com)): # 선택된 재료들의 신맛과 쓴맛의 차이 구하기
            s,b = com[k]
            sour *= s
            bitter += b
        min_gap = min(min_gap, abs(sour-bitter))
print(min_gap)