11047 동전 0

그리디 알고리즘 / 실버 4

 

마찬가지로 매 순간 최적의 해를 찾아 결과를 내는 그리디 알고리즘을 이용하여 문제를 풀었다.

매 순간 최적의 해를 찾기: 뺄 수 있는 가장 큰 수를 빼기를 이용하여 간단하게 문제를 풀었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    private static int n, k, num = 0;
    private static int[] array;

    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        array = new int[n];

        for (int i = 0; i < n; i++){
            array[i] = Integer.parseInt(br.readLine());
        }

        while(k > 0){
            for(int i = n - 1; i >= 0; i--){
                while (k >= array[i]){
                    k -= array[i];
                    num++;
                }
            }
        }
        System.out.println(num);
    }
}