[백준] 그리디 알고리즘 (11047 : 동전 0)

문제

---

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

11047번: 동전 0

---

해설

---

해당 문제는 N 종류의 동전을 가지고 목표한 값을 만들기 위해 필요한 최소의 동전 개수를 구하는 문제이다.

그리디 알고리즘은 그때그때 가장 탐욕적인 (이득이 되는) 선택을 하는 알고리즘으로,

현재 순간에 가장 이득이 되는 경우를 선택해가면 해결할 수 있다.

---

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

위와 같은 예시가 있을 때, 

1000 + 1000 + 1000 + 1000 + 100 + 100을 선택하면 6개의 동전을 통해 목표한 값을 만들어낼 수 있다.

이번 문제는 아주 간단해서 바로 코드 설명으로 넘어가보겠다.

---

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

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

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

        int cnt = 0;
        for (int i = N-1; i >= 0; i--) {
            if(K >= coin[i]){
                cnt += (K / coin[i]);
                K = K % coin[i];
            }
        }
        sb.append(cnt);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

1. 기본적으로 오름차순으로 입력이 주어지기 때문에, 정렬을 해주지 않아도 된다.
2. 목표로 하는 값인 K보다 작거나 같은 동전을 이용하여 K값을 만들어내야하기 때문에,
   사용하고자 하는 동전이 K보다 작다면, 해당 동전을 최대로 사용하는 것이 가장 동전을 적게 사용하는 방법이다.
3. 그렇기 때문에, 사용할 수 있는 만큼 동전을 사용하고 더 이상 해당 동전을 사용하지 못하면 그 다음 동전으로
   나머지 금액을 채워주면 된다.

---

결론

---

오랜만에 그리디 문제를 만나서 반가웠고 난이도가 쉬워서 쉽게 해결할 수 있었던 문제였다.

---