[백준 11047] 동전 0 (JAVA)

백준 11047번 문제  - 동전 0

11047번: 동전 0

---

문제 분석

 

• 가능한 동전 가치 n개를 오름차순으로 입력 받고, 앞서 입력받은 k 값을 만들기 위한 최소한의 동전 수를 구해 출력해라.

---

 

해결 키 포인트

 

• 그리디 알고리즘 이용
• 입력 받고, 동전을 확인할 때는 내림차순으로 확인

 

---

그리디 알고리즘 (탐욕 알고리즘)

 

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

쉽게 말해, 지금의 최선 = 전체의 최선

 

뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 
서울에서 대구의 최솟 값을 선택하고, 대구에서 부산까지의 최솟값을 선택하는 알고리즘

파이썬 알고리즘 인터뷰 (나무위키)

 

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N, K 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 코인 입력
        int coins [] = new int[N];

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

        int count = 0;

        // 가장 큰 수부터 확인하면서 반복
        for(int i=N-1;i>=0;i--) {
            // 만약 현재 돈이 해당 코인으로 나누어진다면
            if(K / coins[i] > 0) {
                // count 증가 및 k에서 코인으로 계산한 금액 제외
                int newCount = K / coins[i];
                K = K - (newCount * coins[i]);
                count += newCount;
            }
        }

        System.out.println(count);
    }
}