백준_2961_도영이가 만든 맛있는 음식

문제

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

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

풀이

1) dfs

해당 음식을 사용할 때와 사용하지 않을 때를 나누어서, 모든 경우를 탐색한다.

코드

import sys
sys.setrecursionlimit(10**6)

N = int(input())
arr = [list(map(int, input().split())) for i in range(N)]

def dfs(p, sour, bitter) : 
    if p+1>=len(arr) : return abs(bitter-sour)
    
    s, b = arr[p+1]
    return min(dfs(p+1, sour*s, bitter+b), # use
               dfs(p+1, sour, bitter)) # not use

ans = float('INF')
for i in range(len(arr)) : 
    ans = min(ans, dfs(i, *arr[i])) # use ith
print(ans)