[백준 | 파이썬3] 11047. 동전0 - 그리디알고리즘

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

11047번: 동전 0

> 그리디 알고리즘

 

가장 큰 단위의 동전가치부터 순회하면서 동전의 가치가 입력받은 k보다 작은 숫자이면 해당 동전으로 k의 가치를 차감할 수 있다는 뜻이다. 따라서 해당 가치로 k를 나눈 몫(몇 번 사용할 수 있는지 그 횟수를 나타냄)을 result에 더해주고 나머지 동전의 가치로 k값을 갱신시킨다. 

여기서 중요한 점은 필요한 동전의 최소 개수를 구하기 위해 가장 큰단위의 동전부터 순회하는 것이다. 만일 작은 동전단위부터 순회한다면 해당 단위에서 동전의 가치가 모두 차감될 수 있기 때문에 최대 개수를 구한 셈이 된다. 따라서 pop(-1)로 리스트의 가장 마지막 동전단위부터 검색하도록 했다.