[BOJ][11047] 동전 0 - JAVA

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

11047번: 동전 0

 

 - 풀이 

 : 탐욕법으로 푸는 문제

 : 동전 갯수의 최소값 = 가장 크게 소모 시킬 수 있는 값

 : Ex 4200 원의 최소 갯수 = 1000원 4장 100원 2장 (단위 중에 1000, 500, 100, 10, 5, 1 밖에 없다면)

 

 

import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = n - 1; i >= 0; i--) {
            if (k == 0) {
                break;
            }
            if (arr[i] > k) {
                continue;
            }

            count += k / arr[i];
            k = k % arr[i];

        }

        System.out.println(count);


    }
}