[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

---

👉 풀이과정

그리디 알고리즘의 대표 문제 동전!!!!!

드디어 풀었잖아~후후

 

제일 먼저 동전 몇 개인지, 합, 동전 종류 입력받는다.

여러 값을 저장해놓고 있어야 하니까 배열 선언해서 저장했다.

배열로 할지 리스트로 할지 살짝 고민했지만 어쨌든!

 

동전의 최솟값을 구해야 하는 문제이니 

큰 값에서부터 값을 확인해야 한다.

작은 값에서부터 확인하면 동전이 많이 나오기 때문!

 

4,600원일 때, 큰 값부터 확인하면 

1,000 * 4 + 500 + 100 => 6개

작은 값부터 확인하면

100 * 46 => 46개가 된다.

 

반복문을 동전갯수만큼 반복하고, 

큰 값부터 확인해야 하니 인덱스를 length - i -1로 주었다.

작은 값을 큰 값으로 나눌 수 없으니 5000원을 지나서 1000원으로 내려오면 

그때부터 연산이 시작된다.

 

동전 갯수를 저장할 변수 cnt에 k / 1000의 값을 넣고,

k는 600원만 남을 수 있게 % 연산을 해서 넣어준다!!!

 

📌 제출코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt(); //동전종류
        int k = scan.nextInt(); //합
        int[] type = new int[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            type[i] = scan.nextInt();
        }
        int length = type.length;
        //맨 뒤에서부터 나누기
        for(int i=0;i<length;i++){
            if(type[length-i-1] <= k){
                cnt += k / type[length-i-1];
                k = k % type[length-i-1];
            }
        }
        System.out.println(cnt);
    }

}