[백준] 11047 동전0

www.acmicpc.net/problem/11047

11047번: 동전 0

문제 설명 : 동전은 총 N종류이고 K 가치의 합으로 만들기 위한 동전 개수의 최솟값을 구하라

 

문제 풀이 :

그리디 알고리즘

최소한의 개수로 만들기 위해서는 가장 큰 동전부터 선택하는 것이 최적의 해가 된다.

동전 K원을 만들기 위해서 오름차순이 되어있는 동전을 맨 뒤에서 부터 확인한다. 만약 동전 K원보다 클 경우 그냥 넘어가고 K원보다 같거나 작으면 몫을 세어준다. 남은 수를 갱신하여 구성할 수 있는 개수를 세주면 된다.

import java.util.Scanner;

public class 동전 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] coin = new int[N];
		int count=0, nmg = 0;
		
		for (int i = 0; i < coin.length; i++) {
			coin[i] = sc.nextInt();
		}

		for (int i = coin.length-1; i >= 0; i--) {
			if(K >= coin[i]) {
				count += K / coin[i];
				K %= coin[i];
				
			}
			
		}
		System.out.println(count);
	
	}
}