탐욕법 알고리즘 예제(2). 백준 [11047] 동전 0

백준[11047] - 동전 0

동전의 종류와 목표금액을 입력받은 뒤 동전들을 이용하여 가장 적은 수의 동전으로 목표금액을 만드는 문제이다.
동전의 종류에 따라 무엇을 선택하는지에 따라 개수가 달라지지만, 이런 문제에는 항상 탐욕법이 정답이 되지는 않는다. 
하지만, 이 예제는 그러한 상황은 배제한 문제인 것 같다.

문제 풀이는 간단하다.
목표금액과 동일하거나 넘지 않는 동전 중 가장 큰 동전을 선택하여 목표금액을 줄여 나가면 되는 문제이다.

다음은 Java로 작성한 코드이다.

import java.util.Scanner;

public class Coin {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int count = 0;

		int n = scan.nextInt();
		int target = scan.nextInt();
		int[] money = new int[n];

		//동전의 종류 입력
		for (int i = 0; i < n; i++) {
			money[i] = scan.nextInt();
		}
		
		//동전 선택
		while(target > 0) {
			for (int i = n-1; i >= 0; i--) {
				if(money[i] <= target) {
					target -= money[i];
					count++;
					break;
				}
			}
		}

		System.out.println(count);
	}

}