[코테 알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

---

현재 상태에서 최선의 해를 선택하는 것이
전체 상태에서 최선의 해라고 가정하는 알고리즘을
'그리디(Greedy) 알고리즘'이라고 한다.

1. 현재 상태에서 최선의 해를 선택한다.
2. 선택한 해가 문제의 제약조건에 벗어나지 않는지 검사한다.
3. 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.

<백준 알고리즘, 11047번>

🎯 동전의 가치가 큰 순서로 합하면 최소 동전의 개수로 해당 가치의 합을 구할 수 있다.
    (오름차순으로 입력되는 동전의 가치가 배수의 관계여서 전체 문제를 해결할 수 있다.)

import java.io.*;
import java.util.*;
class Main {
    static int N;
    static int K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int[] types = new int[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            types[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        for(int i = N-1; i >= 0; i--) {
            int type = types[i];
            if(type <= K) {
                cnt += K / type;
                K %= type;
            }
        }

        System.out.println(cnt);
    }
}