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

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

11047번: 동전 0

 

 

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

---

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력 1

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

예제 출력 1

6

 

예제 입력 2

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

예제 출력 2

12

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]); // 준규가 가지고 있는 동전의 종류
        int k = Integer.parseInt(str[1]); // 동전을 적절히 사용해서 만들어야 하는 가치의 합
        int[] arr = new int[n]; // 동전 종류들을 넣을 배열 생성
        int answer = 0;

        for(int i = 0; i < arr.length; i++){
            arr[i] = Integer.parseInt(br.readLine()); // 동전 종류들을 배열에 넣는다.
        }
        // 문제 조건: 동전의 가치 Ai가 오름차순으로 주어진다.

        /*
            [ 이 문제의 포인트 ]

             구하고하 하는 값: K원을 만드는데 필요한 동전 개수의 최솟값
             ==> 주어진 동전 가치들 중에서 가장 큰 가치(가장 비싼)를 가지고 있는 동전부터 차례대로 얼만큼 필요한지를 구한다

             ex. 1000원
             -> 500원: 2개
                100원: 10개
                 50원: 20개
                 10원: 100개
             이렇게 동전의 가치가 작을 수록 필요한 동전의 갯수는 많아짐 -> 큰 가치의 동전을 최대한 많이 사용하는 것이 가장 적은 수의 동전을 사용하는 방법임.
        */

        for(int i = arr.length - 1; i >= 0; i--){ // 배열의 가장 끝 값 = 배열에 있는 동전들 중 가장 비싼 동전(동전의 가치 Ai가 오름차순으로 주어졌으므로!)
            if(k / arr[i] > 0){ 
                /* 
                    'k / arr[i] > 0'의 의미: 해당 배열의 동전을 가지고 k를 만들 수 있는지 
                    ex. 300원을 500원을 가지고 만들 수는 없음 -> 주어진 값보다 작은 가치의 동전을 써야 한다!
                */
                answer += (k / arr[i]); // 사용할 수 있는 최대 갯수를 answer에 더함
                k = k % arr[i]; // 동전을 사용했으므로 그 만큼을 k에서 차감해줌
                /*
                    ex. 4200원에서 500원짜리를 최대한으로 몇 개 사용할 수 있는지 - 8개
                        -> 500원짜리를 8개 사용했으므로 4200 - 4000(500*8) = 200원이 남음 
                */
            }
        }

        System.out.println(answer);
    }
}