[문제해결을 위한 창의적 알고리즘] 거스름돈 (고급, p156)
거스름돈 문제는 중급에서도 다루었던 문제이다. 그러나 여기에서는 더 큰 숫자에 대해서 처리할 수 있도록 동적 계획법 (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 = new int[10];
Scanner sc = new Scanner(System.in);
m =sc.nextInt();
n = sc.nextInt();
// 최소값을 찾는 것이므로 무한대값으로 초기화
for (int i =0; i <=m; i++)
money[i] = 987654321;
for (int i =0; i<n; i++)
coins[i]=sc.nextInt();
sc.close();
// 모든 동전에 대해서 큰 동전부터 거꾸로 테이블 업데이트
for (int i =n-1; i>=0; i--){
// 동전 값이라면 동전 1개로 해결 가능
money[coins[i]]=1;
// 동전을 한개씩 더해 나가면서 이미 그 금액으로 저장된 동전수가 있으면 1개를 더 추가했을때 더 적은지 확인한다
for (int j =2; j*coins[i]<=m; j++){
if (money[j*coins[i]]>money[(j-1)*coins[i]]+1)
money[j*coins[i]] = money[(j-1)*coins[i]]+1;
}
}
System.out.println(money[m]);
return;
}
}
Big O(n*m): n개의 동전들로 금액 m까지 업데이트해 봄
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/Change156.java