BOJ 2294 - 동전2

www.acmicpc.net/problem/2294

2294번: 동전 2

동적 계획법 문제를 한번도 풀어보지 않아서 오늘은 DP 문제를 골라서 풀어봤습니다.

동적 계획법을 공부하면서 느낀 것은 사전에 공부를 하지 않는다면 실전에서 바로 적용하는 것은 무리가 있다고 판단했습니다. 그래서 미리 미리 사전에 관련 문제를 학습하고 풀이하는 과정이 필요한 것 같습니다.

동적 계획법을 공부하면서 제가 이해한 것은 이미 정해진 해답들 속에서 관련된 규칙을 도출해 점화식을 만들어 푸는 것입니다. 그래서 상향식 접근법(Bottom-up)이라고 혼자 편리하게 생각하기로 했습니다.

위 문제에서는 주어진 동전의 가치 K를 구하는 방식 중 가장 동전의 개수가 작은 방식을 구하면 됩니다. 

위 예제에서 예로든 15원을 구하는 방법을 생각해보면 15원을 구하는 경우의 수는 이미 정해져 있습니다. 그러나 그 많은 경우의 수 중 가장 최소의 동전 수를 갖는 방식을 찾는게 어렵고 문제의 해답일 뿐입니다.

그렇다면 15원을 트리 형태로 아래로 가지쳐서 나가는 그림을 그리게 된다면 모든 경우의 수를 파악할 수 있을 것이며, 가장 아래의 뿌리부터 올라가는 상향식 접근 방법으로 무언가 규칙을 찾을수도 있을 것입니다.

대충 그려서 정렬도 잘 되지 않은 그림이지만 위의 처럼 최소 경우의 수를 트리 형태로 그려서 나타낼 수 있으며 0에서부터 15까지 올라가는 식을 세울 수도 있습니다.

0번째는 아무것도 선택하지 않았으니까 dp[0] = 0 으로 초기화 해주고 나머지는 최대값으로 초기화 해준 후 최소 값을 비교해 나가면서 점화식을 세웁니다.

dp[i] = Math.min(dp[i], dp[i - coin[j]] + 1)의 점화식을 세우면서 문제를 해결할 수 있습니다.

public class boj2294 {

    static int[] coin = new int[10005];
    static int[] dp = new int[10005];
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Arrays.fill(dp,1000000);

        for(int i=0; i<n; i++) {
            coin[i] = sc.nextInt();
        }

        dp[0] = 0;

        for(int i=1; i<=k; i++){
            for(int j=0; j<n; j++){
                if(i >= coin[j]){
                    dp[i] = Math.min(dp[i], dp[i - coin[j]] + 1 );
                }
            }
        }
        System.out.print(dp[k] > k ? -1 : dp[k]);

    }

}