거스름돈
-
[문제해결을 위한 창의적 알고리즘] 거스름돈 (고급, p156)알고리즘 2017. 2. 2. 13:30
거스름돈 문제는 중급에서도 다루었던 문제이다. 그러나 여기에서는 더 큰 숫자에 대해서 처리할 수 있도록 동적 계획법 (Dynamic Programming)으로 푸는 방법을 살펴보도록 하겠다. 아이디어는 1부터 주어진 금액까지의 배열을 만들고 각 동전으로 만들 수 있는 금액들을 만들어 보면서 동전이 가장 작은 숫자로 업데이트하는 방식이다. 해설에 설명된 것보다 좀 더 직관적으로 이해할 수 있는 방법으로 구현해 보았다. import java.util.Scanner; public class Change156 { public static int[] money = new int[10001]; public static void main(String[] args){ int m; int n; int[] coins = ..