본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임
문제
문제 풀이
이러한 거스름돈 문제는 그리디로도 풀 수 있는데, 여기서는 화폐 단위가 큰 단위가 작은 단위의 배수가 아니기 때문에 그리디로는 해결할 수 없고 DP로 해결해야 한다.
적은 금액부터 큰 금액까지 확인가며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화페 개수를 $a_i$ , 화폐의 단위를 k라고 했을 때, 금액 i-k를 만들 수 있는 최소한의 화폐 개수인 점화식 $a_(i-k)$는 다음과 같다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 화폐의 개수 n , 타깃 m 을 입력받기
n , m = map(int, input().split())
# n 개의 화폐 단위 정보를 입력받기
arr = []
for i in range (n):
arr.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화(타깃 m). 특정 화폐를 만들 수 있는 경우의 수
d = [ 10001 ] * ( m + 1 )
# 다이나믹 프로그래밍( Dynamic Programming ) 진행(보텀업)
d[0] = 0
for i in range(n): # 화폐 개수 만큼 loop
for j in range(arr[i], m + 1): # 테이블에서 현재 화폐 arr[i] 보다 작은 수는 업데이트 할 필요가 없음. arr[i]로 만들 수 있는 경우의 수 이므로
if d[j-arr[i]] != 10001: # ( i - k )원을 만드는 방법이 존재하는 경우. 현재 화폐 arr[i] 빼주는 건 고정인 거 참고
d[j] = min(d[j], d[j - arr[i]] + 1 )
# 계산된 결과 출력
if d [ m ] == 10001 : # 최종적으로 M 원을 만드는 방법이 없는 경우
print (- 1 )
else :
print(d[m])
예시
예를 들어 n = 3, k =7 이고, 각 화폐 단위가 2, 3, 5라고 하자.
10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다. M의 최대 크기가 10,000이므로 이렇게 설정했다. 0원인 경우 화폐를 하나도 사용하지 않으면 만들 수 있으므로 테이블 값을 0으로 설정한다. 초기 테이블은 다음과 같다.
화폐 단위 2부터 확인한다.
이어서 화폐 단위 3을 확인한다.
마지막으로 화폐 단위 5를 확인한다.
결과적으로 7원을 만들기 위한 최소의 화폐 개수는 2이다.