[전체 코드]

import java.util.*;

public class Main {
    static int n, k, cnt = 0;
    static int[] monies;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();

        monies = new int[n];
        for (int i = 0; i < n; i++) {
            monies[i] = sc.nextInt();
        }

        // values 오름차순 정렬 후 뒤집기
        Arrays.sort(monies);

        int[] reversedMonies = new int[n];
        for (int i = 0; i < monies.length; i++) {
            reversedMonies[i] = monies[n - (i + 1)];
        }

        for (int money : reversedMonies) {
            cnt += k / money;
            k %= money;
        }

        System.out.println(cnt);
    }
}

[문제 풀이 설명]

이 문제는 전형적인 그리디 알고리즘인 잔돈 문제이다.

예제 입력을 보면, 4200원을 총 10개의 입력받은 동전을 적절히 사용해서 그 가치의 합을 K로 만들 때 필요한 동전 개수의 최솟값을 구하는 것이다.
한 마디로, 입력 받은 동전으로 4200원을 만들 때 사용되는 동전의 개수를 최소로 하면 몇 개의 동전이 필요한지?를 묻는 질문이다.

전형적인 그리디 알고리즘 사용 문제다.

우선 그리디 알고리즘은 매 경우마다 최적의 해를 도출해내는 방법이므로 최솟값을 구할 수 있고, 최적의 해를 도출해야 하므로 입력받은 동전을 내림차순으로 정렬한다.

정렬 후, 동전 하나씩 반복하면서 cnt += k / money; 와 k %= money; 을 작성해주면 된다.
cnt는 반환해야 할 동전의 최소 개수이고, money는 나눴을 때 나머지값으로 계속 갱신해주면 된다.

[어려웠던 점]

오랜만에 보는 알고리즘이라 처음에 헷갈렸다.
그리고 /와 % 연산자를 능숙하게 사용하지 못했다.

[느낀점]

다양한 알고리즘을 많이 알아두고, 문제 풀기 전에 생각을 하자 생각. 🤔