[Java] 백준(실버-4) 11047번 - 동전 0

문제 풀이

---

이번 문제는 그리디 알고리즘을 이용해 풀 수 있는 단순한 문제이다.

아이디어 도출

주어지는 동전들을 보면 서로 배수 관계에 있음을 알 수 있다. 여기서 그리디 알고리즘을 어떻게 적용할 수 있을까? 여기서는 최적해를 찾아나가면 되기 때문에 K원을 만들 때 최소한의 개수를 구해야 한다. 결국, 가장 큰 가치를 지닌 동전부터 선택하고 넘어가면 된다는 것이다.

즉, 주어지는 N개의 동전들 중에서 가장 큰 가치를 지닌 동전부터 탐색해가며 K보다 크다면 넘어가고, 작다면 K원을 만들 수 있는 개수를 더해가면 된다. 그러면 자연스럽게 가장 큰 가치의 동전부터 개수를 세게 된다.

가장 큰 가치의 동전부터 탐색하는 방법은 다음과 같다.

가장 큰 가치의 동전부터 탐색하는 방법은 쉽다. 이 문제에서 주어진 동전들은 오름차순으로 주어지기 때문에 이를 반대로 탐색한다면? 가장 큰 가치의 동전부터 탐색할 수 있다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    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());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        // 동전들을 담을 배열
        ArrayList<Integer> coinList = new ArrayList<>();
        // K원이 되기 위한 동전 개수를 담을 변수
        int coinCnt = 0;

        // 입력받은 N개의 동전을 coinList에 저장
        for(int i=0; i<N; i++) {
            int A = Integer.parseInt(br.readLine());
            coinList.add(A);
        }

        // 오름차순으로 주어진 동전 배열을 내림차순으로 탐색하며 K원을 만들 수 있는지 확인한다.
        for(int i=N-1; i>=0; i--) {
            System.out.println(coinList.get(i) + "원, " + K / coinList.get(i) + " " + K % coinList.get(i));
            // K원이 될 수 있는 가장 큰 가치의 동전부터 개수를 구해나간다.
            // 즉, 현재 동전이 K원보다 작거나 같아야한다.
            if(K >= coinList.get(i)) {
                // coinCnt 변수에 현재 동전으로 K원을 만들 수 있는 개수를 더해준다.
                coinCnt += (K / coinList.get(i));
                // 이후, K원에서 현재 동전의 개수만큼 차감시켜준다.
                K = K % coinList.get(i);
            }
        }
        bw.write(coinCnt+"\n");

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

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.