[백준 19942번-파이썬] 다이어트

http://acmicpc.net/problem/19942

{코드}

def calculate(do, picked, pick_sum):
    global chosen, tot_prc
    if pick_sum[4] >= tot_prc:
        return
    for i in range(4):
        if req_nut[i] > pick_sum[i]:
            break
    else:
        chosen = picked.copy()
        tot_prc = pick_sum[4]
        return
    if do == n:
        return

    picked.append(do+1)
    for i in range(5):
        pick_sum[i] += nuts[do][i]
    calculate(do+1, picked, pick_sum)

    picked.pop()
    for i in range(5):
        pick_sum[i] -= nuts[do][i]
    calculate(do+1, picked, pick_sum)
    return


inf = 9876543210
n = int(input())
req_nut = tuple(map(int, input().split()))
nuts = tuple(tuple(map(int, input().split())) for _ in range(n))
chosen = []
tot_prc = inf

calculate(0, [], [0]*5)

if tot_prc == inf:
    print(-1)
else:
    print(tot_prc)
    print(*chosen)

{설명}

이 문제는 모든 경우의 수를 확인해야 하기 때문에 DFS를 사용하여 문제를 풀게 됩니다.

먼저 입력을 받은 후 DFS, 즉 calculate 함수가 실행됩니다.

먼저 현재 비용이 현재 최소 비용보다 크면 최소 비용이 업데이트 되지 않고 같으면 사전순으로 앞선 것이 이미 저장되어 있기에 무시합니다.

그 후, 만약 고른 식재료들의 영양소들의 합이 최소 영양소 기준보다 크다면 최소 비용과 고른 영양소를 업데이트합니다.

만약 하나라도 최소 기준보다 작으면 테스트할 영양소인 do를 포함한 결과와 포함하지 않은 결과를 모두 calculate합니다.

만약 do가 n 이상이면 해당하는 영양소가 존재하지 않으므로 바로 리턴합니다.

마지막에 최소 비용이 없데이트 되지 않았다면 -1을 아니면 최소 비용과 선택한 영양소들을 출력합니다.