동전교환은 다이나믹 프로그래밍으로 해결한다.
잔돈이 n 이고, c가 코인일때
f(n) = f(n - c) + 1
가 된다.
현재 잔돈에서 코인을 뺀돈의 코인개수가 있다면 거기에 +1을 하게 되면 현재의 코인개수가 된다.
반응형
'알고리즘 > 정올' 카테고리의 다른 글
| [정올][백트래킹] 1027 좋은 수열 (0) | 2016.10.09 |
|---|---|
| [정올][그리디] 2499 저울 (0) | 2016.10.07 |
| [정올] [문제은행] 1942 하얀모자 (0) | 2016.09.23 |
| [정올][다이나믹] 1871 줄세우기 (0) | 2016.09.21 |
| [정올][다이나믹] 1539 가장높은 탑 쌓기 (0) | 2016.09.20 |