[문제해결을 위한 창의적 알고리즘] 거스름돈 (고급, 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

문제해결을 위한 창의적 알고리즘 목록