[BOJ][Python]14916번 풀이

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

14916번: 거스름돈

t = [-1 for _ in range(100001)]
t[2],t[4],t[5],t[6],t[7],t[8] = 1,2,1,3,2,4
for i in range(9,100001):
    t[i] = min((t[i-2]+t[2]),(t[i-5]+t[5]))
print(t[int(input())])

이번에도 평이한 난이도의 문제입니다만 생각을 어떻게 하는지에 따라 결론에 다다르는 시간이 다를 것 같네요. 일단 가장 적은 갯수의 동전을 반환하기 위해서는 뭐가 됐든 숫자가 늘 때 1개만 늘어나는게 가장 바람직한 일이죠. 따라서 모든 경우가 완벽히 이상적으로 잘 이뤄진다고 가정하고 1개씩만 늘어날 수 있는 경우인 2원과 i-2원의 조합과 5와 i-5의 조합 중 더 작은 것을 집어넣으면 끝이라고 생각했습니다. 저 경우에 -1이 나오는 1과 3이 절대 개입을 하지 않을 위치까지는 미리 입력을 해줘야 하니 반복문은 9부터 시작하도록 구성했구요.

 

물론 dp가 아닌 방법으로 푸신다면 몫과 나머지를 이용해서 5를 최대한 쓰는 방식으로 해보시면 될 것 같습니다(5로 나눴는데 나머지가 2로 나눠떨어진다면 5와 2의 몫을 더하고, 나눠떨어지지 않는다면 5의 몫에서 1을 빼고 나머지가 2로 나눠떨어지는지 계산하시면 될 것 같네요). 

 

개인적으로는 해당 방법이 가장 빠를 것 같아서 이렇게 해봤는데요. 혹시 반복문의 시작이 9보다 낮으면서 깔끔한 풀이를 발견하신 분은 댓글로 알려주시면 감사하겠습니다.