[이코테] 효율적인 화폐 구성

문제 내용

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M 원이 되도 록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며，사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원，3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

 

입출력 예시

입력

2 15 # N 가지 종류의 화폐, 원하는 가치의 합 M

2 3 # 화폐 종류

 

출력

5

 

풀이방법

점화식을 세우는데, 일단 그 방법이.. 해당 금액에 맞는 코인이 있으면 일단 바로 1을 넣어둔다.

그리고 그 외에 없는 것들은 차례대로 채워주면 되는데.. for 문을 돌면서 [구하고자 하는 금액 - 해당 코인] + 1 을 해주면 된다.

이게 뭔가 값을 점층적으로 쌓을 수 있다면 dp로 풀수 있다 보면 될것 같다. 

이게 점화식으로 쓰는 것으로 책에선 가르쳐주지만, 일단 기본적인 아이디어부터 머릿속에 그림을 그리는 연습부터 잘 하면 굳이 수식까진 안짜도 될것같다. (난이도가 높지 않아서 그런가...?)

 

INF = 999999999
N,M = map(int,input().split())
dp = [INF for _ in range(0,M+1)]
coins = list(map(int, input().split()))
for i in range(0, N):
    coin = coins[i]
    if(coin <= M):
        dp[coin] = 1
for i in range(0,M+1):
    item = dp[i]
    for j in range(0, N):
        coin = coins[j]
        if(i - coin >= 0): dp[i] = min(dp[i - coin] + 1, dp[i])
print(dp[M] if dp[M] != INF else -1)