[백준 / python] 22115: 창영이와 커피

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

문제

창영이는 커피를 좋아한다. 회사에 도착한 창영이는 아침 커피를 즐기려고 한다.

회사에는 N개의 커피가 각각 하나씩 준비되어 있고, 각 커피에는 카페인 함유량 Ci가 있다.

창영이는 N개의 커피 중 몇 개를 골라 정확히 K만큼의 카페인을 섭취하려고 한다.

창영이가 정확히 K만큼의 카페인을 섭취하기 위해서는 최소 몇 개의 커피를 마셔야 할까?

입력

첫째 줄에 커피의 개수 N, 창영이가 섭취해야 하는 카페인의 양 K가 주어진다.

둘째 줄에 N개 커피의 카페인 함유량 Ci가 주어진다.

풀이

배낭 문제

import sys

N, K = map(int, sys.stdin.readline().split())
coffees = list(map(int, sys.stdin.readline().strip().split()))

dp = [[sys.maxsize if i != 0 else 0 for i in range(K+1)]
      for _ in range(N+1)]

for i in range(1, N + 1):
    caffeine = coffees[i-1]
    for j in range(1, K + 1):
        dp[i][j] = dp[i-1][j]
        if j < caffeine:
            continue
        if dp[i-1][j-caffeine] != sys.maxsize:
            dp[i][j] = min(dp[i][j], dp[i-1][j-caffeine] + 1)

if dp[-1][K] == sys.maxsize:
    print(-1)
else:
    print(dp[-1][K])