동전 교환(냅색 알고리즘)

동전의 종류가 많으면 DFS로 풀면 시간 초과가 난다.

 

coin[i]는 동전의 종류가 들어있는 배열 [1, 2, 5]

dy[i]는 i라는 금액을 만드는데 필요한 동전의 최소 갯수

 

coin[i]=1원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐

coin[i]=2원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐

coin[i]=5원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐

dy[j - coin[i]] + 1의 의미는 기존 거슬러준 동전의 갯수에서 해당 동전의 종류를 하나 더 사용한다는 의미이다.

dy[5 - coin[1]] + 1의 의미는 3원에서 거슬러준 동전의 갯수 에다가 2원을 하나 더 사용한다는 의미이다.(5원)

 

dy[15]를 구한다.

 

i = 0일 때 (1원을 사용할 것임)

j = 1 ~ 15까지 돈다.

dy[1] = Math.min(dy[1], dy[1-coin[0]+1); = 1 1원 하나

dy[2] = Math.min(dy[2], dy[2-coin[0]+1); = 2 1원 하나 + 1원 하나

...

dy[15] = Math.min(dy[15], dy[15-coin[0]+1); = 1원 14개 + 1원 하나

-> 14원에서 거슬러준 동전의 갯수에다가 1원을 하나 더 사용한다.

 

i = 1일 때

j = 2 ~ 15까지 돈다.

dy[2] = Math.min(dy[2], dy[2-coin[1]+1); = 1 2원 하나

dy[3] = Math.min(dy[3], dy[3-coin[1]+1); = 2 1원 하나 + 2원 하나

dy[4] = Math.min(dy[4], dy[4-coin[1]+1); = 2 2원 하나 + 2원 하나

...

dy[15] = Math.min(dy[15], dy[15-coin[1]+1); = 1원 하나 + 2원 여섯 + 2원 하나 

-> 13원에서 거슬러준 동전의 갯수에다가 2원을 하나 더 사용한다.

 

i = 2일 때

j = 5 ~ 15까지 돈다.

dy[5] = Math.min(dy[5], dy[5-coin[2]+1); = 1 5원 하나

...

dy[15] = Math.min(dy[5], dy[15-coin[2]+1); = 3 5원 두개 + 5원 하나

-> 10원에서 거슬러준 동전의 갯수에다가 5원을 하나 더 사용한다.

 

dy[15] = 3;

 

import java.util.*;
class Main{
    static int n, m;
    static int[] dy;
    public int solution(int[] coin){
        //dy배열을 큰 숫자로 초기화
        Arrays.fill(dy, Integer.MAX_VALUE);
        dy[0]=0;
        //1,2,5원
        for(int i=0; i<n; i++){
            //1원 부터 거스름돈 갯수 구해서 배열에 넣기
            for(int j=coin[i]; j<=m; j++){
                //기존 거스름돈의 동전 갯수보다 작으면 바꿔줘야한다.
                //2원 -> 1원 2개 -> 2원 1개 이런식으로
                dy[j]=Math.min(dy[j], dy[j-coin[i]]+1);
            }
        }
        //거슬러줄 동전의 최소갯수이므로 dy[15]에 담긴거 리턴
        return dy[m];
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt(); //동전의 종류 갯수
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }//동전의 종류 배열
        m=kb.nextInt(); //거슬러줄 금액
        dy=new int[m+1];
        System.out.print(T.solution(arr));
    }
}