[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍

상당히 어렵게 다가왔다.
아무래도 수학을 놓고 산지 오래여서 그런지 모르겠지만, 점화식에 대해서 이해를 하는데에도 좀 오래 걸렸던 것 같다.

약간의 무식한 방법을 통해서 이해하려고 애를 써보기도 했다..

효율적인 화폐구성

효율적인 화폐 구성을 풀면서 헤맸던 이유를 생각해보자면,

1. 처음 대략적인 접근을 할 때에는, 목표 금액까지를 dp 배열에 둔 다음, 각각의 화폐 단위 구성에 따라 각각의 금액을 설정해줘야겠다는 접근은 했다. (대충 시작은 좋았던 듯 싶다.)

2. 그 다음 금액별로 화폐구성을 찾아주면서 답을 찾아냈어야 했는데, 여기서 어떻게 접근해야할지 하나도 몰랐다.

// 목표금액 k, 화폐 단위 갯수 num, 각각의 화폐 금액 money[]
import java.io.*;
import java.util.*;

public class Solution {
    public int solution(int num, int k, int [] money){
        int [] dp = new int [k+1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        for(int i=0 ; i<num ; i++){
            for(int j=money[i] ; j<=k ; j++){
            	if(dp[j - money[i]] != 10001)
                	dp[j] = Math.min(dp[j], dp[j - money[i]] +1);
            }
        }
        if(dp[k] == 10001)
            return -1;
        else
            return dp[k];
    }
}

답을 알고 나서도 시원하게 와닿지는 않는다.. 며칠 뒤 다시 풀어봐야겠다.

어떻게 풀어야 할까

어쨌든 다이나믹 프로그래밍을 공부하면서 느낀 것은

1. 당연하지만, 점화식 찾아내기

2. max 또는 min 값을 통해 적절한 값을 dp 배열 안에 집어 넣기.

3. 바텀-> 업이 나을지, 업->바텀 구조가 나을지 고민

이 세 가지를 유의해서 풀이를 하는 것이 중요한 것 같다.
지금도 다시 풀었던 문제를 보면 시원하게 풀이가 떠오르지가 않는다.
아무래도 여러 번 풀면서 친해질 필요가 있는 것 같다..