동전 교환 알고리즘

[문제]

 

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

• $50 한 장을 훔친다
• $20 두 장, $10 한 장을 훔친다
• $20 한 장, $10 세 장을 훔친다
• $10 다섯 장을 훔친다

 

 

냅색 알고리즘

유명한 다이나믹 프로그래밍 문제 중 하나입니다.

 

위의 문제를 풀기 전에 간단하게 1, 2, 5, 10 원 동전들이 있고, 이 동전들로 10원을 만드는 방법을 구해보겠습니다.

 

d [i][j] = i 가지 종류의 동전을 사용하여 j 금액을 만드는 경우의 수라고 가정을 해봅니다.
그러면 저희가 구할 수는
d [4][10] = 4가지 ( 1,2,5,10 ) 종류의 동전을 사용하여 10원을 만드는 경우의 수

 

• 풀이

1.  [ 코인을 저장할 coin 배열 ] [ 동전 개수를 저장할 dy배열 ] 을 생성
2.  dy[j] = j원을 거슬러 주기 위해 사용된 동전의 최소 개수
3. 코인별로 거슬러 줄 동전 개수를 계산하고 dy에 저장

 

 

아래의 표를 보고 이해해보겠습니다.

d [1][2] = 1원으로 2원을 만드는 방법 1가지

 

d [2][2] = 0원에 2원을 추가해 2원을 만드는 방법 1가지 ( d[2][0] ) + d [1][2]

d [2][3] = 1원에 2원을 추가해 3원을 만드는 방법 1가지 + 1원으로 3원 만드는 방법 1가지 ( d[2][1] + d[1][3] )

d [2][4] = 2원에 2원을 추가해 4원을 만드는 방법 + 1원으로 4원 만드는 방법

                 ( ( d[2][0] + d[2][2] )+ ( d[1][2] + d[2][2] ) + d[1][4] )

d [2][5] = 4원에 1원 추가하는 방법 ( 2 ) + 1원으로 5원

....

 

 

public class CoinChange {
    public static void main(String[] args) {
        int[] coin = {10,20,50};

        long result = napsac(50,coin);
        System.out.println(result);
    }

    public static long napsac(int target, int[] type){

        long[] dy = new long[target+1];
        // 인덱스 1부터 시작

        dy[0] = 1;
        // 최소의 개수인 1부터 시작

        for(int i=0; i<type.length; i++){

            for(int j=1; j<=target; j++){
                if(type[i] <= j){
                    dy[j] += dy[j-type[i]];
                    /*
                    ex.
                    type[i] = 10, j=11일때,
                    dy[11-10] = dy[1]
                    dy[11] += dy[1]
                    즉, dy[11] 자리에 dy[1] 의 값을 더해준다.
                    */
                }
            }
        }
        return dy[target];
    }
}