[백준] 동전 0 (java) Greedy

2020-02-12

동전 0 (백준 > 11047 > Greedy)

문제 링크

문제설명

준규가 가지고 있는 동전은 총 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


풀이

package Greedy;

import java.util.*;

class beak_동전0{
	//20min
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int arr[] = new int[n]; int idx = 0;
        
        
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            //같은 자리수라는게 1000 5000도 될 수 있다. 그치만... 될거 같았는데ㅠ
//            if(String.valueOf(arr[i]).length() == String.valueOf(k).length())
//                idx = i;
        }
        
        int answer = 0;
        for(int i = n-1; i>=0; i--){
            if(k>=arr[i]) {
	            answer = answer + k/arr[i];
	            k = k%arr[i];
	        }
        }
        
        System.out.println(answer);
    }
}


후기 (20min)

음.. 빠르게 구하겠다고 같은 자리숫자의 크기에 도달하는 idx를 구해서 그 idx부터 시작하려고 했는데 뭔가 에러가 난거같다.. 그래서 그냥 끝부터 돌림