백준 11047번 동전 0 (JAVA)

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

11047번: 동전 0

 

저는 그리디를 통해 문제를 풀었습니다.

큰 돈으로 먼저 환전해주면 적은 개수로 할 수 있기에 큰 돈 먼저 많이 한전해주는 쪽으로 하고, 환전가능하면, 그 다음에는 환전 방법을 찾지 않도록하여 시간초과가 나오지 않게 하였습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Test {

    public static void main(String[] args) throws Exception {
        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[] money = new int[n];
        for(int i = 0 ; i < n ; i++){
            money[i] = Integer.parseInt(br.readLine());
        }
//        Arrays.sort(money);
        int result = cal(n-1,k,money,n);
        System.out.println(result);
    }
    private static final int INF = 987654321;
    private static boolean findResult = false;
    private static int cal(int depth, int left, int[] money, int n) {
        if(findResult){
            return INF;
        }
        if(left == 0){
            findResult = true;
            return 0;
        }
        if(depth < 0){
            return INF;
        }
        int result = INF;
        for(int i = left/money[depth] ; i >= 0 ; i--){
            result = Math.min(result, cal(depth-1,left - i * money[depth],money,n) + i);
        }
        return result;
    }

}