[백준 Python] 19942번 다이어트

백준 파이썬 19942번 다이어트

Gold 4

 

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

import sys
input = sys.stdin.readline
def recur(idx, a, b, c, d, price, pick):
    global ans, rst
    if idx == n:
        if a>=my[0] and b>=my[1] and c>=my[2] and d>=my[3]:
            if price <= ans:
                ans = price
                rst.append(pick)
        return
    recur(idx+1,a,b,c,d,price,pick)
    recur(idx+1, a+ingre[idx][0], b+ingre[idx][1], c+ingre[idx][2], d+ingre[idx][3], price+ingre[idx][4], pick+[idx+1])
    
n = int(input())
my = list(map(int, input().split()))
ingre = [list(map(int, input().split())) for _ in range(n)]
ans = 9999999999
rst=[]
recur(0,0,0,0,0,0,[])
rst.sort()
if ans == 9999999999:
    print(-1)
    exit()
print(ans)
print(*rst[0])

재귀로 푼 문제

선택하는 경우와 선택하지 않는 경우를 나눠주면 되는 간단한 문제다.