[백준 2961번] 도영이가 만든 맛있는 음식 파이썬 풀이

도영이가 만든 맛있는 음식 

1 초

128 MB

15352

8516

6219

54.022%

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

예제 입력 1

1
3 10

 

예제 출력 1

7

예제 입력 2

2
3 8
5 8

예제 출력 2

1

예제 입력 3

4
1 7
2 6
3 8
4 9

예제 출력 3

1

2, 3, 4번 재료를 사용한다면, 요리의 신맛은 2×3×4=24, 쓴맛은 6+8+9=23이 된다. 차이는 1이다.

 

 

전형적인 브루트포스 문제이다. 재료를 1개부터 n개 선택하는 모든 경우의 수에 대하여, 파이썬 라이브러리 itertools의 combination을 이용하여

신맛과 쓴맛을 계산한후, 두 값의 차이를 기존의 최소값과 비교하는 과정을 반복해주면 된다.

 

예를 들어 주어진 재료(n)가 3개있다고 가정한다면, 재료를 1개부터 3개까지 고를 수 있을것이고 1개를 고를때 나올 수 있는 조합과, 2개를 고를때 나올 수 있는 조합, 3개를 고를 때 나올 수 있는 조합에서 신맛은 서로 곱하고, 쓴맛은 서로 합하여 최종 신맛과 쓴맛을 구한후에 두 값의 차를 절대값으로 하여 기존의 최소값과 비교하는 과정을 반복하는것이다.

 

위 아이디어를 코드로 옮기면 다음과 같다.

import sys
from itertools import combinations
n = int(input())
# 재료 정보 (신맛, 쓴맛) 입력받기
food = [list(map(int, input().split())) for _ in range(n)]

result = sys.maxsize  # 신맛과 쓴맛의 최소값

# 재료를 1개부터 n개 선택하는 모든 경우의 수
for i in range(1, n+1):
    # 재료를 i개 선택하는 모든 경우 => selected_food
    for selected_food in combinations(food, i):
        # 신맛, 쓴맛 초기화
        sour, written = 1, 0
        # 선택된 재료들을 대상으로 신맛 쓴맛 계산
        for s, b in selected_food:
            sour *= s  # 신맛은 재료들의 곱
            written += b  # 쓴맛은 재료들의 합
        # 최종적으로 쓴맛과 신맛의 차가 가장 적게 되어야함
        # 기존 최소값과 비교하여 작은값 업데이트
        result = min(abs(sour-written), result)

# 모든 경우의 수를 돌려봤을 때
# 쓴맛과 신맛의 최소값 출력
print(result)

 

 

https://www.acmicpc.net/problem/2961

2961번: 도영이가 만든 맛있는 음식