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

[iamRecoder]

▣ 입력예제 1 3 125 15 ▣ 출력예제 1 3

import java.util.*;
class Main{
    static int n, m;
    static int[] dy;
    public int solution(int[] coin){
        Arrays.fill(dy, Integer.MAX_VALUE);
        dy[0]=0;
        for(int i=0; i<n; i++){
            for(int j=coin[i]; j<=m; j++){
                dy[j]=Math.min(dy[j], dy[j-coin[i]]+1);
            }
        }
        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));
    }
}

[iamRecoder]

• 최소 동전의 수를 저장하는 dy 배열에 최대 동전의 수를 저장한다.
• j번째 값에서 coin만큼의 값을 빼고 +1한 값(coin을 사용한 경우)과 이전의 값을 비교한다