[Baekjoon] 11047번 동전 0 (Java)

생각보다 정말 쉬운 문제였다. 시간 초과에 자주 걸려서 이번에도 시간이 초과될까봐 걱정했는데 다행히 한 번에 통과했다.

예제 입력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.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String[] num = scan.nextLine().split(" ");
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0; i < Integer.parseInt(num[0]); i++){
            int x = Integer.parseInt(scan.nextLine());
            boolean boo = Integer.parseInt(num[1]) > x;
            // 정해진 금액을 만들어야 되는 문제이기 때문에 해당 금액보다 작거나 같은 수만 저장
            if(Integer.parseInt(num[1]) >= x){  
                arr.add(x);
            }
        }
        int cnt = 0;
        int y = Integer.parseInt(num[1]);   // 원하는 금액
        // 오름차순으로 저장되어 있기 때문에 해당 금액(y)에 가장 가까운 동전으로 먼저 만듦
        for(int i = arr.size()-1; i >= 0; i--){
            // 해당 금액보다 작거나 같은 수로만 만듦
            if(y >= arr.get(i)){
                int n = y / arr.get(i);
                y = y % (arr.get(i)*n);     // 해당 금액에 가장 가깝게 만들고 나머지로 다시 금액을 맞춤
                cnt += n;
                if(y == 0){break;}
            }
        }
        System.out.println(cnt);
    }
}