달나라 토끼를 위한 구매대금 지불 도우미 [17212]
2021. 10. 31. 16:19ㆍ학습/Python
반응형
17212번: 달나라 토끼를 위한 구매대금 지불 도우미
달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은
www.acmicpc.net
- DP 문제로 바텀-업으로 풀게되었다.
- 동전이 1,2,5,7원 으로 이루어져있으므로 li[1] li[2] li[5] li[7] 자리에 동전이 1개 있다는 의미로 1을 채워 넣는다.
- 그 이후 동전의 금액을 쌓아가면서 **리스트의 현재 동전수**와 **일정금액(1,2,5,7)을 뺀 금액의 동전수 +1** 을 비교를 해서 최소를 구한다.
Code : URL
반응형