문제정의
- N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.
- 예를 들어 2원, 3월 단위의 화폐가 있을 때는 15원을 만들기 위해 3월을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다.
- M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.
입력조건
- 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10000)
- 이후의 N개 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
출력조건
- 첫째 줄에 최소 화폐 개수를 출력한다.
- 불가능 할 때는 -1을 출력한다.
입출력예시1
# 입력
2 15
2
3
# 출력
5입출력예시2
# 입력
3 4
3
5
7
# 출력
-1정답코드
n, m = map(int, input().split(" ")))
array = []
for i in range(n):
array.append(int(input()))
n = 3
m = 7
array = [2,3,5]
array.sort(reverse=False)
# 한 번 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [10001] * (m+1) # 0원 ~ 목표금액까지가 인덱스, 각 금액까지 필요한 화폐개수가 값인 리스트
d[0] = 0 # 0원은 0개의 화폐가 필요한 것으로 초기화
for i in range(n): # 각 화폐 단위(i)에 대해
for j in range(array[i], m + 1): # 각 화폐 단위 ~ 목표 금액까지 각 금액(j)에 대해
if d[j-array[i]] != 10001: # 현재 금액(j)에서 화폐 단위(i)를 뺀 금액을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j-array[i]] + 1) # 현재 금액(j)의 최소 화폐 개수 설정,
if d[m] == 10001:
print(-1)
else:
print(d[m])정리
- n은 화폐 종류의 개수입니다.
- m은 목표 금액입니다.
- array에는 화폐 단위들이 들어있습니다. 각 화폐의 단위는 array[j] 입니다.
- d[i]는 금액 i 를 만들 수 있는 최소한의 화폐 개수입니다.
- 점화식은 아래와 같습니다.
각 화폐 단위 j를 하나씩 확인하며,
d[i-array[j]]를 만드는 방법이 존재하는 경우, d[i] = min(d[i], d[i-array[j]]+1) 입니다.
d[i-array[j]]를 만드는 방법이 존재하지 않는 경우, d[i]는 10001(무한)으로 남습니다.
로직
- d는 다음과 같이 초기화합니다.
# 0원에 필요한 화폐 개수는 0개로 초기화합니다.
목표금액까지(인덱스) 0 1 2 3 4 5 6 7
필요한 회폐 개수(값) 0 10001 10001 10001 10001 10001 10001 10001- 첫 번째 화폐 단위인 2를 확인하고 점화식에 따라 값을 업데이트합니다.
# 0번 인덱스의 값인 0을 기반으로 2, 4, 6의 값이 업데이트 됩니다.
목표금액까지(인덱스) 0 1 2 3 4 5 6 7
필요한 회폐 개수(값) 0 10001 1 10001 2 10001 3 10001- 두 번째 화폐 단위인 3을 확인하고 점화식에 따라 값을 업데이트합니다.
# 위와 같은 방식으로 3, 6, 7을 업데이트합니다. 예를 들어 7은 4원(인덱스, 7-3)에 값이 있으니, 거기서 1을 더한 값을 업데이트합니다.
목표금액까지(인덱스) 0 1 2 3 4 5 6 7
필요한 회폐 개수(값) 0 10001 1 1 2 10001 2 3- 세 번째 화폐 단위인 5을 확인하고 점화식에 따라 값을 업데이트합니다.
# 위와 같은 방식으로 5, 7을 업데이트합니다. 예를 들어 7은 (2+2+3)에서 (2+5)로 업데이트합니다.
목표금액까지(인덱스) 0 1 2 3 4 5 6 7
필요한 회폐 개수(값) 0 10001 1 1 2 1 2 2
yozzum