DP2

아이템 선택 문제

동전을 n개 주고
m의 거스름돈을 준다고 할때 최소로 줄 수 있는 동전의 수를 찾는 문제이다.

접근방식은 다음과 같다.

1. dp[0] = 0이다.

2. 만약 j번째 동전을 뽑는다고 하면, i의 값이 j번째 동전의 값 coin[j] 보단 커야한다. 작다면 그 자리에 들어갈 수 없기 때문이다.

3. 마지막 사용한 동전이 j라면, 그 전까지 사용한 합은 i - coin[j]이다. 해당상태는 dp[i-coin[j]]인데 이 값들 중 가장 작은 값으로 갱신해야 한다.

import sys

n, m = tuple(map(int, input().split()))

temp = list(map(int,input().split()))
coin = [0] + temp
dp = [sys.maxsize] * (m + 1)
dp[0] = 0

for i in range(1, m+1): # dp loop
    for j in range(1, n+1): # coin loop
        if i >= coin[j]: # i must be bigger than coin value 
            dp[i] = min(dp[i-coin[j]] + 1, dp[i])

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

혹은 가끔씩 반대로 가장 많은 동전을 물어보기도 하는데 이때는 반대로 max를 찾으면 된다.