N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 만들어라. 각 화폐는 몇 개라도 사용할 수 있다.
a. 예를 들면
2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해서는 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수다.
b. 입력 조건
- 첫째 줄에 N, M이 주어진다
- 1 <= N <= 100
- 1 <= M <= 10,000
- 이후 N개 줄에 각 화폐의 가치가 주어진다.
- 화폐의 가치는 10,000보다 작거나 같은 자연수
c. 출력 조건
- 첫째 줄에 경우의 수 X를 출력한다.
- 불가능할 때는 -1을 출력한다.
코드
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
'문제풀이 > DP' 카테고리의 다른 글
[파이썬] [DP] 개념 정리 (0) | 2022.01.24 |
---|---|
[파이썬] [DP] 백준 18353 병사 배치하기 (0) | 2022.01.24 |
[파이썬] [DP] 금광 (0) | 2022.01.24 |
[파이썬] [DP] 1로 만들기 (0) | 2022.01.24 |
[파이썬] [DP] 개미전사 (0) | 2022.01.24 |