[BOJ - DP] 14916번 : 거스름돈 ( python )

백준알고리즘 - 동적계획법 Dynamic Programing - 14916번 거스름돈 파이썬

 

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

 

 

 

오랜만에 DP를 풀었더니 개념도 제대로 생각 안나고 해서 아예 처음 보듯 쉬운것부터 시작했다.

결론적으론 혼자서 못 풀것 같아서 사람들의 답을 보면서 그들이 어떻게 점화식을 유도했는지를 중점적으로 보았다. 12일 오늘까지는 유도하는 과정을 좀더 배우고 내일부터는 직접 점화식 유도를 해봐야겠다.

 

---

 

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

 

---

 

사고하기

• 목표 : 거스름돈 동전의 최소개수, 거슬러 줄 수 없을땐 -1
• 유형 : DP

 

거스름돈이 n월일 때 2원짜리와 5월짜리를 합쳐 최소개의 동전으로 돌려주어야한다.

1원부터 14원까지 쭉 나열을 해보았다.

 

아래를 보면 5~9까지, 10~14까지... 에는 규칙이 있다.

5원의 개수 : 10101, 21212, 32323 ... 의 반복

2원의 개수 : 03142의 반복

 

그리고 전체 개수를 비교하면 10원부터는 i원의 개수는 (i-5)원+1개인것을 확인할 수 있다.

 

---

<점화식 유도 과정>

1원 : 2원, 5원으로는 구성할 수 없으므로 -1 출력

2원 : 2원 *1개

3원 : -1

4원 2*1

5원 : 51 + 20 >> 1개

6원 : 50 + 23 >> 3개

7원 : 51 + 21 >> 2개

8원 : 50 + 24 >> 4개

9원 : 51 + 22 >> 3개

10원: 52 + 20 >> 2개 : (5원) + 1개

11원: 51 + 23 >> 4개 : (6원) + 1개

12원: 52 + 21 >> 3개 : (7원) + 1개

13원: 51 + 24 >> 5개 : (8원) + 1개

14원: 52 + 22 >> 4개 : (9원) + 1개

---

 

따라서 d라는 변수를 만들어 0~9원까지는 static으로 값을 넣어주고,

10원부터 n원까지는 (i-5)에필요한 개수 + 1개를 넣어주면 된다.

 

 

정답코드

 

import sys
input = sys.stdin.readline

n = int(input())
    #0  1 2  3 4 5 6 7 8 9
d =[-1,-1,1,-1,2,1,3,2,4,3]
for i in range(10,n+1):
    d.append(d[i-5]+1)
    
print(d[n])