[백준] 11047번 : 동전 0 – JAVA [자바]

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

11047번: 동전 0

 

---

• 문제

 

 

---

• 문제 풀이

백준 11047번 동전 0은 실버 4 난이도의 그리디 문제이다. 이 문제에서는 동전의 종류 개수 N개와 이 동전들을 이용해서 만들어야 하는 총 합 K가 주어진다. 그리고 입력으로 동전의 가치들이 오름차순으로 주어진다. 이때, K원을 만드는데 필요한 최소 동전 개수를 구하면 된다.

 

우선 예를 보면서 한번 보겠다.

 

EX 1) N = 10, K = 4200

1

5

10

50

100

500

1000

5000

10000

50000

위에 있는 표와 같이 동전들이 주어졌다. 물론 4200원을 만드는데 1원짜리 동전을 4200개를 써서 만들 수도 있지만 최소 개수를 구하려면 가치가 가장 큰 동전들을 먼저 이용해야 한다. 

 

50000원, 10000원, 그리고 5000원은 4200원을 초과하기 때문에 이용할 수 없다. 그다음은 1000원이다. 1000원짜리 동전을 4개까지 쓸 수 있다. 그러면 200원이 남는다.

 

이제 1000원보다 더 작은 동전들을 본다. 500원은 이 200원을 초과하기 때문에 100원짜리로 넘어가는데 100원짜리 동전 2개를 쓰면 200원을 만들 수 있다. 따라서, 4200원을 만드는데 필요한 최소 동전의 개수는 6개다.

 

이 예시에서 볼 수 있듯이 우선 동전의 가치들을 배열에 저장한다. 그리고 가장 큰 값부터 확인하는데 이 값을 X라고 하겠다. 그리고 사용해야 하는 최소의 동전 개수를 count라고 하겠다.

 

만약에 X > K이면 X보다 작은 동전으로 넘어가고 X ≤ K이면 count를 (K / X)만큼 더해준다 K = K - (K / X)로 업데이트해준다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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/coins[i]);
                k -= (k/coins[i])*coins[i];
            }
        }
        System.out.print(count);
    }
}