Algorithm (PS)

[백준] 2961 Python

minjiwoo 2022. 10. 13. 19:07
728x90

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

 

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

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

www.acmicpc.net

브루트포스로 풀었다

재료를 1개 선택하는 경우부터 2개, 3개, ... n개까지 선택하는 경우 각각의 조합 경우의 수를 따져봤다. 

그리고 신맛과 쓴맛의 차이의 최솟값이 나올 때마다 갱신했다. 

from itertools import combinations

data = []
n = int(input())
for _ in range(n):
    s, b = map(int, input().split())
    data.append((s, b))

min_diff = int(1e9)
for k in range(1, n+1): # 1개 이상 n개 이하까지 선택할 수 있음
    for case in list(combinations(data, k)): # k 개 선택하는 경우
        temp_s = 1
        temp_b = 0
        for c in case:
            temp_s *= c[0]
            temp_b += c[1]
        min_diff = min(min_diff, abs(temp_s - temp_b))
print(min_diff)
728x90