동전교환

동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.

입력 설명

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,
그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다.

출력 설명

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

입력

3
1 2 5
15

출력

3

힌트

출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

틀린 구현 코드

public class 동전교환 {
    static int n;
    static int m;
    static int[] coins;
    static int answer = Integer.MAX_VALUE;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); //동전 종류 개수
        coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = in.nextInt();
        }
        m = in.nextInt(); //거슬러줄 금액

        dfs(0, m, 0);
        System.out.println(answer);

    }

    //    static void dfs(int i, int sum, int count){
//        System.out.println("sum: "+sum);
//        if(sum==m && count<=answer){
//            answer = count;
//            return;
//        }
//        else{
//            if(i==3) i = 0;
//            dfs(i+1,sum+coins[i],count+1);
//            dfs(i+1,sum,count);
//        }
//    }

    static void dfs(int i, int sum, int count) {
        System.out.println("sum :"+sum+" count: "+count);
        if(sum<0) return;
        if (sum == 0 && count <= answer) {
            answer = count;
            return;
        } else {
            if (i == 3) i = 0;
            dfs(i + 1, sum - coins[i], count + 1);
            dfs(i + 1, sum, count);
        }
    }
}

처음에 생각했던 방법은 재귀호출로 sum에 동전 금액을 더하는 경우, 안더하는 경우로 index를 점점 높이면서 재귀호출 하는 방식으로 구현. 두번째는 전체 sum에서 동전을 빼는 경우 안빼는경우를 두가지 계속해서 호출해서 sum이 0이 되고 count가 최소일때 리턴하는 방식을 생각했음. 위와 같이 구현하니 무한한 재귀호출로 java.lang.StackOverflowError가 발생.

모범답안 참고 후 구현 코드

 static int n;
    static int m;
    static int[] coins;
    static int answer = Integer.MAX_VALUE;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); //동전 종류 개수
        coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = in.nextInt();
        }
        m = in.nextInt(); //거슬러줄 금액

        dfs(0,0);
        System.out.println(answer);

    }


    static void dfs(int L,int sum){
        //L: 동전의 개수
        //sum: L개 동전 금액의 총합
        if(L>=answer) return;
        if(sum>m) return; //무한 안돌려면 이게 필요
        if(sum==m){
            answer = Math.min(L,answer);
        }
        else {
            for (int i = n-1; i >= 0; i--) {
                dfs(L + 1, sum + coins[i]);
            }
        }
    }

기초하는 아이디어 자체는 다를게 없지만 멈추는 조건을 덜 달았음. sum>m일때 멈춰야하고 동전개수가 answer보다 많은 경우는 더 볼필요 없으므로 중단해야함.