[백준] 19942번 다이어트 ★

💡문제접근

• 3중 반복문을 사용한다는 점에서 조금 비효율적인 코드지만 백트래킹 방법으로 접근하는 방법이 수월하지 않아 파이썬 순열과 조합 라이브러리인 Combinations를 사용했다.

💡코드(메모리 : 31256KB, 시간 : 168ms)

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input())
mp, mf, ms, mv = map(int, input().strip().split())
nutrients = [[]]
for _ in range(N):
    p, f, s, v, c = map(int, input().strip().split())
    nutrients.append((p, f, s, v, c))

min_price = 9999999999      # 최소 비용
for i in range(1, N+1):
    for comb in combinations(range(1, N+1), i):
        tp, tf, ts, tv, tc = 0, 0, 0, 0, 0
        for j in comb:
            tp += nutrients[j][0]
            tf += nutrients[j][1]
            ts += nutrients[j][2]
            tv += nutrients[j][3]
            tc += nutrients[j][4]
        if tp >= mp and tf >= mf and ts >= ms and tv >= mv:
            if min_price > tc:
                min_price = tc
                answer = comb
            elif min_price == tc:
                answer = sorted((answer, comb))[0]

if min_price == 9999999999:
    print(-1)
else:
    print(min_price)
    print(*answer)

💡소요시간 : 47m