[백준-그리디] 11047번: 동전0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

풀이: 

k원을 만드는데 필요한 동전 개수의 최솟값을 구해야 하므로 큰 단위의 동전부터 N원을 만드는데 사용하면 된다.

코드:

import java.util.Scanner;

//https://www.acmicpc.net/problem/11047
public class p11047 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] coins = new int[n];
        for(int i =n-1; i>=0; i--){
            coins[i] = sc.nextInt();
        }

        int result = 0;
        int residual = k;
        for (int coin : coins){
            if(coin <= k){
                result += residual/coin;
                residual %= coin;
            }
        }

        System.out.println(result);
    }
}