DP- 효율적인 화폐 구성

DP(Dynamic Programming) 기법
해결한 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 캐싱 기법을 활용하여 문제의 시간 복잡도를 줄이는 문제 해결 기법. -> 탑다운(재귀함수),바텀업(반복문) 활용 가능

✅ 문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 회폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
불가능할 때는 -1을 출력한다.

입력 예시 1
2 15
2
3

출력 예시 1
5

입력 예시 2
2 15
2
3

출력 예시 2
5

💻 코드

import java.util.*;

public class DP_Exercise3 {

    static int[] dp = new int[10001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();

        Integer[] a = new Integer[n];

        for(int i = 0; i < n; i++)
        {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        Arrays.fill(dp, 10001);
        dp[0] = 0;

        for(int i = 0; i < n; i++)
        {
            for(int j = a[i]; j <= m; j++)
            {
                if(dp[j - a[i]] != 10001)
                    dp[j] = Math.min(dp[j], dp[j - a[i]] + 1);
            }
        }
        if(dp[m] == 10001) System.out.println(-1);
        else System.out.println(dp[m]);
    }
}

📝 정리

어떤 점화식을 사용할 지 계속 고민했으나.. 결국 풀리지 않아 참고했던 문제이다. 이전에 풀은 문제를 참고해서 케이스를 나누어 숫자를 더하려했으나 복잡해서 간단화하여 풀려고 했고 그 과정에서 이 점화식을 구성하는 게 어려웠다. 결국 DP 문제는 dp 테이블 제작 이후 인덱스 0부터 차례로 예시를 들어 구성해보고 그 속에서 규칙성을 찾는 것이 관건인 것 같다. 수학 문제 같은..