📌 문제
도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.
지금 도영이의 앞에는 재료가 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이다.📌 풀이
💬 Code
import sys, itertools
from itertools import combinations
input = sys.stdin.readline
n = int(input())
sour = []
bitter = []
for _ in range(n):
a, b = map(int, input().split())
sour.append(a)
bitter.append(b)
diff = float('inf')
for i in range(1, n+1): # 재료를 i개 뽑을 때
idxs = list(combinations(list(range(n)), i)) # 가능한 경우를 담은 리스트
for food in idxs: # 경우 하나씩 탐색
s = 1
b = 0
for j in range(i): # 맛 계산
s *= sour[food[j]]
b += bitter[food[j]]
if abs(s - b) < diff:
diff = abs(s - b)
print(diff)💡 Solution
신맛은 sour에, 쓴맛은 bitter에 입력 순서대로 저장하고, 재료를 몇 개 섞어서 음식을 만들어야 하는지 제한이 주어지지 않았기 때문에 1개부터 n개까지 모든 경우의 수를 다 봐야 한다. → Brute Frorce
따라서 combinations를 사용해 1개 뽑는 경우, 2개 뽑는 경우, …를 idxs에 리스트로 담아두었다. 예제 3의 경우를 보자. 재료가 총 4개이므로 print(idxs)를 추가하면 이런 모양으로 출력된다.
# 입력
4
1 7
2 6
3 8
4 9
# sour은 [1, 2, 3, 4], bitter은 [7, 6, 8, 9]가 됨
# 출력
[(0,), (1,), (2,), (3,)] # i == 1, 즉 1개 뽑는 경우
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] # i == 2, 즉 2개
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)] # i == 3, 즉 3개
[(0, 1, 2, 3)] # i == 4, 즉 4개(0, 1, 3)을 예로 들면 0번째, 1번째, 3번째 재료를 뽑은 경우다. 즉, 신 맛은 sour에서 0, 1, 3번째 값을 곱해 1×2×4=8가 되고, 쓴 맛은 bitter에서 0, 1, 3번째 값을 더해 7+6+9=22가 되어 둘의 차이는 14가 된다. 이 값이 여태까지 차이 중 최솟값이라면 최솟값을 갱신한다.
