[PS|DP] 백준 창영이와 퇴근

0. 문제 

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

22115번: 창영이와 커피

---

1. 문제 해설

아래 힌트에 이 문구가 있다.

커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라.

 

그리고 위에도 볼드채로 '하나씩' !! 이라고 쓰여 있는데 이걸 놓치면 틀릴 수 있다. .. ㅠ

---

2. 문제 풀이

그래서 이 DP+냅색 문제를 두 가지 경우로 바꾸어서 이해해 보았다.

먼저, 만약 커피가 무제한으로 존재한다면? 아래와 같이 풀 수 있을 것이다.

N, K = map(int,input().split())
C = list(map(int,input().split()))
# DP[카페인] = 커피의 최소 갯수
DP = [float('inf') for _ in range(K+1)]
#init
for i in C:
    DP[i] = 1

for i in range(K+1):
    if DP[i]!=float('inf'):
        for j in range(i):
            if DP[j]!=float('inf'):
                if i+j<K+1:
                    DP[i+j] = min(DP[i+j], DP[i]+DP[j])
if DP[K]==float('inf'): print(-1)
else:
    print(DP[K])

 

하지만 위 문제처럼 

커피가 단 한개씩만 존재해야 한다면, 
아래와 같이 커피 i를 사용하여 카페인을 채우는 경우는 커피 i-1까지를 사용한 경우에 반영시켜주면 된다.
이렇게 차곡차곡 반영시켜 dp 테이블의 정의는 dp[i번째 커피까지를 썼을 때][j만큼의 카페인을 채우는] = 커피 최소 갯수 
로 나타낼 수 있다.

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

dp = [[0] + [float('inf')] * K for _ in range(N + 1)]

## dp[i번째 커피까지를 썼을 때][j만큼의 카페인을 채우는] = 커피 최소 갯수

for i in range(1, N+1):
    for j in range(K+1):
        if j+arr[i-1]<=K:
            dp[i][j+arr[i-1]] = min(dp[i-1][j+arr[i-1]], dp[i-1][j]+1)
        dp[i][j] = min(dp[i][j], dp[i-1][j])

# for i in dp:
#     print(i)
if dp[N][K]==float('inf'): print(-1)
else:print(dp[N][K])

'''
test case
8 100
90 5 4 2 2 2 2 2

5
'''