백준[19942] 다이어트 (Python3)

문제 자체는 쉬웠지만, 최적의 경로를 사전 순으로 빠른 것을 출력하란 것 때문에 생각이 좀 필요했던 문제.
하지만, 그렇게 어렵게 생각할 필요는 없는 문제였다.

최적의 답을 찾기 위해, 재료를 순서대로 탐색하며 먹을지, 안 먹을지 결정하면 된다.
즉, 매 순간 2가지 선택지가 있으므로, 2^15만큼의 시간 복잡도가 필요하다.
따라서 백트래킹을 사용해 문제를 풀이했다.

사전 순으로 빠르게 출력하란 것은 내가 첫번째 인덱스부터 탐색을 했다면, 신경쓸 필요가 없다.
왜냐하면, 백트래킹 탐색 순서가 낮은 인덱스부터 차례대로 올라가기 때문이다.

탐색한 경로를 리스트 형태로 관리하면서, 기존보다 적은 비용으로 목표 영양소를 섭취할 수 있다면 기존 값을 교체한다.

백트래킹을 쓰지 않는 경우, 파이썬이라면 i tertools를 사용해 가능한 모든 조합을 만들어 탐색하는 방법이 있다.

 

from collections import deque

N = int(input())
mp, mf, ms, mv = map(int, input().split())
ans, MAX = [], float("inf")
foods = [0]
for i in range(N):
    foods.append(list(map(int, input().split())))


def recur(p, f, s, v, price, index, visit):
    global MAX, N
    if p >= mp and f >= mf and s >= ms and v >= mv:
        if price <= MAX:
            if price < MAX:
                ans.clear()
            MAX = price
            ans.append(visit)

    if N + 1 == index:
        return
    recur(p + foods[index][0], f + foods[index][1], s + foods[index][2], v + foods[index][3],
          price + foods[index][4], index + 1, visit + [index])
    recur(p, f, s, v, price, index + 1, visit)


recur(0, 0, 0, 0, 0, 1, [])
if MAX == float("inf"):
    print(-1)
else:
    print(MAX)
    for i in ans[0]:
        print(i, end = " ")