탐욕법 - 거스름돈 알고리즘, 동전교환 알고리즘

 

탐욕법의 가장 대표적인 알고리즘으로 문제에 필요한 금액이 입력되면 가지고 있는 동전의 조합으로 해결하는 문제이다. 주어진 숫자 N을 충족하기 위해 동전의 배열에서 가장 큰 값부터 조건에 만족하면 추가하는 식으로 문제를 해결한다.

 

public class coinChange {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N = 164;
		int ary[] = { 1, 5, 10, 50 };

		int cnt = 0;
		for (int i = ary.length - 1; i >= 0; i--) {
			while (N > 0) {
				if (N >= ary[i]) {
					N -= ary[i];
					cnt++;
				} else {
					break;
				}
			}
		}
		System.out.println(cnt);// 코인의 개수

		int n = 164;
		int ary1[][] = { { 1, 0 }, { 5, 0 }, { 10, 0 }, { 50, 0 } };

		for (int i = ary1.length - 1; i >= 0; i--) {
			while (n > 0) {
				if (n >= ary1[i][0]) {
					n -= ary1[i][0];
					ary1[i][1]++;
				} else {
					break;
				}
			}
		}
		for (int i = 0; i < ary1.length; i++) {
			System.out.println(ary1[i][1]);//각각의 코인의 개수
		}
	}
}