동전교환(냅색)

dp 문제는 경우를 쪼개서 보는게 중요한 것 같다..

 

냅색 알고리즘을 이용해서 푼다

M원을 거슬러 줘야할때 1~M까지 인덱스의 dy배열을 만들어서 최대값으로 초기화한 후

dy[0] = 0(0원 거슬러주는 방법은 0)으로 하고

tmp = dy[j - coin[i]] +1 <- dy 배열에 coin[i] 코인을 사용하는것, 무조건 1개 는 사용하니 +1, 이 값이 1원으로 만든 dy 배열의 값 보다 작으면 그 값을 넣어주기

import java.util.*;

class Main{
    static  int[] dy;
    static int n,m;
    public int Solution(int[] coin){
        Arrays.fill(dy,Integer.MAX_VALUE); //더 작은 횟수를 구하면서 비교하기 위해 일단 최대값으로 초기화
        dy[0] = 0; //0원은 가능한 경우가 없으니 0으로 초기화
        for (int i = 0; i < n; i++){ //동전 금액별로 돌면서
            for (int j = coin[i]; j <= m; j++){
                // dy배열을 coin[i] 금액 인덱스부터 돌면서 그 금액을 뺀 것 +1 로 가능한 값이 현재 dy값 보다 작으면 dy 값을 교체
                int tmp = dy[j - coin[i]] + 1;
                dy[j] = Integer.min(tmp,dy[j]);
            }
        }
        return dy[m];
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] coin = new int[n];
        for (int i = 0; i < n; i++) coin[i] = in.nextInt();
        m = in.nextInt();
        dy = new int[m+1]; //1~m까지 금액을 dy 배열 인덱스에 맞게 넣어줌
        System.out.print(T.Solution(coin));
    }
}