[백준 🥇5] 22115번 창영이와 커피 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

그동안 봐오던 배낭 문제와 유형이 약간 달라서 헤맸다😭
아직 배낭문제를 완전히 이해하지 못했나보다

n, k = map(int, input().split())
c = [0] + list(map(int, input().split()))

dp = [[1000000] * (k + 1) for _ in range(n+1)]   # dp[i][j] = i번째 커피까지 확인했을 때 카페인 양이 j인 커피의 최소 개수
for i in range(n+1):
    dp[i][0] = 0

for i in range(1, n+1):
    for j in range(1, k+1):
        if j < c[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-c[i]] + 1)

if dp[n][k] == 1000000:
    print(-1)
else:
    print(dp[n][k])