1. 문제 설명 📌

설명이 직관적이라 추가 설명 생략

2. 접근 방식 🗃️

KEY WORD: Greedy Algorithm

동전 수가 무한하기 때문에 Greedy 알고리즘을 적용하면 된다. Greedy 알고리즘은 매 순간 최적의 선택을 하는 것이다. 여기서 최적의 선택은 가능한한 큰 단위의 동전을 사용하여 동전 개수를 줄이는 것이다. 따라서 내림차순으로 동전 단위를 하나씩 훑으며, K원을 최대한 큰 단위의 동전으로 차감한다.

내림차순으로 동전 조회
만약 현재 조회 중인 동전으로 K원을 나눌 수 있다면? 나눈 몫만큼 동전을 사용 가능한 것임으로 몫을 답에 누적시킴
K원은 (해당 동전의 단위 x 몫) 만큼 차감되었으므로, 나머지만큼만 남아있는 것이다. 따라서 K = K%단위로 갱신한다.
1,2,3번을 K == 0이 될때까지 반복

3. 코드 소개 🔎

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

public class Main {
    public static void main(String[] args) throws IOException {
        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 [] units = new int [N];

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

        int ans = 0;
        for(int i = N-1; i >= 0; i--){
            if(K/units[i] != 0) {
                ans += K/units[i];
                K = (K%units[i]);
            }
            if(K == 0) break;
        }
        System.out.println(ans);
    }
}