백준/11047번/Java - 동전 0 (그리디)

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

그리디 알고리즘을 활용하는 문제.

 

1.최적이라 생각하는 선택지를 고르고 조건에 부합하는 지 검사한다.

2.선택한 해가 문제를 해결하는지 검사한다.

3.해결하지 못하면 다시 다른 선택지를 고른다.

 

이번 문제에서는 주어진 동전으로 K원을 맞춰야 하는 문제이다.

예제를 보면 오름차순으로 주어진 10 종류의 동전을 활용해 4200원을 만들어야 한다.

동전을 최소로 사용해야 하므로 최적의 선택지는 가장 큰 동전을 활용하는 것이다.

(문제에서 주어진 동전들은 서로 배수, 약수 관계이므로 가장 큰 동전부터 택하는 것이 가장 동전을 적게 쓸 수 있는 방법이다)

가장 큰 동전인 50000원 동전을 사용하면 문제를 해결할 수 없으므로, 다음으로 큰 10000원 동전을 선택, 10000원도 해결이 안되니까,

5000원, 5000원도 안되니까 1000원을 선택한다.

1000원을 선택하면 1000원 동전 4개를 사용하여 4000원을 만들 수 있다.

 

따라서 남은 목표는 4200원이 아닌 나머지 200원이 된다.

 

이러한 반복을 통해

1000 * 4 + 100 * 2 로 동전 6개를 활용한 4200원을 만들 수 있다.

 

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

public class Main {

    static int N;
    static int K;
    static int count = 0;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];

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

        for(int i=N-1; i>=0; i--){
            if(K == 0) break;
            int coin = arr[i];

            if(coin <= K) {
                count += K / coin;
                K = K % coin;
            }
        }

        System.out.println(count);


        br.close();
        bw.flush();
        bw.close();
    }
}