📝 문제

실버1 문제 풀다가 시간초과에서 도저히 해결이 안되길래 도망쳐 온 문제😭
그리디 알고리즘을 이용해서 푸는데
동전이 오름차순으로 정렬되어 있는 점을 이용해서
동전의 가격이 저장된 배열을 역순으로 탐색하여
k - 동전의 가격 > 0 인 순간에 그 동전의 가격을 k에서 빼고 동전의 수를 카운트했다.

📌 코드

package Baekjoon;

import java.io.*;
import java.util.*;


public class BOJ11047 {
    public static void main(String[] args) throws IOException{
        // 큰 동전부터 탐색하면서 n > 동전의 가격일 때 카운트
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        int cur = k;
        int answer = 0;

        while(cur > 0){
            for(int i = n-1; i >= 0; i--){
                if(cur - tokens[i] < 0) continue;
                cur -= tokens[i];
                answer++;
                break;
            }
        }
        System.out.println(answer);
    }
}