[백준22115/골드5] 창영이와 커피 - Python

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

 

dp 다 까먹어서 요즘 dp 문제를 풀었다.

이 문제는 9465번 스티커처럼 커피를 마실때, 안마실 때 구분해서 dp 배열에 저장해서 풀면 되는 줄 알고 엄청 헤맸다.

14782 벼락치기처럼 dp 배열을 바꿨더니 풀렸다.

 

1. dp K+1 크기의 1차원 리스트로 생성

2. 커피 하나씩 순회하면서 그 커피를 마실 때 가능한 카페인 합 거꾸로 순회하면서 커피의 최솟값 갱신

 

N, K = map(int, input().split())
coffees = list(map(int, input().split()))

dp = [float('inf')] * (K + 1)
dp[0] = 0

for c in coffees:
    # 전체 카페인을 하나씩 거꾸로 순회하면서 현재 커피를 마실 경우 커피 수의 최솟값 갱신
    for i in range(K, c - 1, -1):
        dp[i] = min(dp[i], dp[i - c] + 1)

print(dp[K] if dp[K] != float('inf') else -1)