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

문제 링크

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

구현 방식

• 백트래킹으로 구현해주었다
• visit 1차원 리스트로 재료를 중복하여 사용하는 경우를 제거해 주었다
• dfs 함수 인자에 idx를 넘겨주어 더 효율적인 탐색이 가능하도록 해줌

코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
tastes = []
for n in range(N): S, B = map(int, input()[:-1].split()); tastes.append((S, B))

def dfs(idx, s, b):
    global min_diff
    if idx != 0: min_diff = min(min_diff, abs(s-b))

    for i in range(idx, N):
        if not visit[i]:
            visit[i] = True
            dfs(idx+1, s*tastes[i][0], b+tastes[i][1])
            visit[i] = False


min_diff = int(10e9); visit = [False]*N
dfs(0, 1, 0)
print(min_diff)