효율적인 화폐 구성

💻 입력 조건

• 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

💻 출력 조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

💻 입력 예시1

2 15
2
3

💻 출력 예시1

5

💻 입력 예시2

3 4
3
5

💻 출력 예시2

-1

📖 문제 해결
화폐들끼리 배수의 관계가 아니므로 그리디 알고리즘이 아닌 다이나믹 프로그래밍 알고리즘을 이용하여야 해결할 수 있는 문제입니다. 가장 작은 화폐의 단위부터 가장 큰 화폐의 단위까지 차례대로 반복문을 수행하고, 반복문 내에서는 만들 수 있는 금액들에 대하여 최소로 필요한 화폐의 개수를 계산하여 메모장에 입력해 주는(혹은 업데이트해주는) 방식으로 문제를 해결하였습니다.

# n과 m을 입력받기
n, m = map(int, input().split())

# n가지 종류의 화페를 입력받기
coins = []
for i in range(n):
    coins.append(int(input()))

# 메모를 위한 리스트 d를 
# 길이가 m+1이고 10001의 값으로 이루어진 리스트로 초기화
d = [10001] * (m+1)

# 0원은 0개의 화폐로 구성할 수 있으므로 d[0] = 0
d[0] = 0

# 점화식에 맞춰 중첩 반복문 작성
for i in range(n):
    for j in range(coins[i],m+1):
        if d[j-coins[i]] != 10001:
            d[j] = min(d[j], d[j-coins[i]]+1)

# 만약 m원의 값을 만들 수 있다면 만들기 위해 필요한 최소 화폐의 개수를 출력
if d[m] != 10001:
    print(d[m])

# 불가능하다면 -1 출력
else:
    print(-1)