이코테_효율적인 화폐구성

문제

문제
N가지 종류의 화폐가 있다.
이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
입력 조건
첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
출력 조건
첫째 줄에 경우의 수 X를 출력한다.
불가능할 때는 -1을 출력한다.

입력 예시1
2 15
2
3
출력 예시1
5

입력 예시2
3 4
3
5
7
출력 예시2
-1

풀이

이 전에 포스팅했던 백준 문제 동전 1과 비슷하면서도 다른 문제이다.
m + 1 길이의 dp 배열을 만들어두고 각 값을 INF로 초기화 한다.
그리고 주어진 동전들로 만들 수 있는 경우들을 확인하는데
for coin in coins:
for i in range(coin,m+1):
if d[i - coin] <= INF:
d[i] = min(d[i],d[i-coin]+1)
이 부분에서 i-동전을 했을 때 만들 수 있는 경우가 존재하면 현재 dp 배열에 저장된 값과 i-동전 인덱스 부분의 값에서 1을 더한 값을 비교해서 최솟값을 넣어주는 과정을 반복하면 최종적으로 각 배열에는 인덱스 만큼의 가치를 만들기 위한 동전의 최소개수가 저장된다.

풀이코드

import sys
input = sys.stdin.readline

INF = 987654321
n,m = map(int,input().split())
coins = list(int(input()) for _ in range(n) )

d = [INF] * (m+1)
d[0] = 0



for coin in coins:
    for i in range(coin,m+1):
        if d[i - coin] < INF:
            d[i] = min(d[i],d[i-coin]+1)

if d[m] == INF:
    print(-1)
else:
    print(d[m])