Coding Test/이것이 코딩 테스트다
[이코테 다이나믹 프로그래밍] 효율적인 화폐 구성
Lucian_Cho
2021. 1. 10. 05:05
# 문제
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
# 입력 예시 2
3 4
3
5
7
# 출력 예시
# 출력 예시 1
5
# 출력 예시 2
-1
내 풀이
n, m = map(int, input().split())
value = [int(input()) for _ in range(n)]
dp = [0] * (m + 1)
for i in range(1, m + 1):
# 보유한 화폐 하나로 구성할 수 있는 금액인 경우
if i in value:
dp[i] = 1
continue
for v in value:
# (i - v) 금액의 화폐 구성이 가능하고 아직 i 금액의 화폐 구성을 안해본 경우
if dp[i - v] != 0 and dp[i] == 0:
dp[i] = dp[i - v] + 1
# (i - v) 금액의 화폐 구성이 가능하고 이미 i 금액의 화폐 구성 시도가 있었던 경우
if dp[i - v] != 0 and dp[i] != 0:
dp[i] = min(dp[i], dp[i - v] + 1) # 최소 화폐 개수 체크
if dp[m]:
print(dp[m])
else:
print(-1)