DP - 점화식을 찾자 (백준 1463번 1로 만들기)

백준 1463번 1로 만들기 문제에서...

 

dp[n] 을 n을 1로 만드는 최소횟수라 생각하자.

DP 문제에서 가장 중요한 것은 점화식을 찾는 것이다.

 

(3으로 나눌 수 있다면) dp[n] = dp[n/3] + 1 이다.

(2로     나눌 수 있다면) dp[n] = dp[n/2] + 1 이다.

                  1을 뺀다면 dp[n] = dp[n-1] + 1 이다.

 

(어떤 작업을 한다면) dp[n] (현재 작업의 횟수는) = dp[작업하기 전의 횟수] + 1 (어떤 작업) 이다.

 

예시로, dp[12] = min(dp[4] + 1, dp[6] + 1, dp[11] + 1) 이며, 이는 12를 1로 만드는 최소 연산 횟수이다.

3가지 중에 가장 최소의 값을 찾아 갱신하는 것이다.

물론 dp[4] 또는 dp[6]을 참조하기 전에 3이나 2로 나눠질 수 있는지 먼저 계산한 후 나눠질 수 있다면 참조해야 한다.

 

초기값은 dp[0] = dp[1] = 0 이다.

 

정답 코드는 아래와 같다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        System.out.println(dp[N]);

 

아래 필기를 게시글로 옮긴 것이다.