DP(Dynamic Programming)

DP(Dynamic Programming) 알고리즘은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 즉,

여러 하위 문제를 푼 후, 그 결과를 (점화식 등의 형태로) 쌓아올려 주어진 문제를 해결하는 것이다.

이런 성질을 최적 부분 구조(optimal substructure)와 중복 부분 문제(overlapping subproblems)라고 한다.

DP 알고리즘의 일반적인 접근 방법은 다음과 같다.

1. 작은 문제 정의: 큰 문제를 작은 문제로 쪼개기 위해 규칙을 찾아 정의한다.
2. 작은 문제 해결: 작은 문제를 해결한다. 이때, 이미 해결된 작은 문제의 결과를 저장하고 재활용한다.
3. 큰 문제 해결: 작은 문제의 해결 결과를 이용하여 큰 문제를 해결한다.

구현 자체는 그렇게 어렵지 않으니, 실제 예제를 들어 풀어보자.

(BOJ 1463 - 1로 만들기.)
https://www.acmicpc.net/problem/1463

먼저 문제의 요구 조건인 '최소 횟수'를 만족하는 배열을 DP라고 놓겠다.
예를 들어 DP[4]에 들어있는 값의 경우 다음과 같은 경우가 발생할 수 있다.

1. 4 / 2 / 2 = 1 (2번)
2. 4 / 2 - 1 = 1 (2번)
3. 4 - 1 - 1 - 1 = 1 (3번)

이 중 최소값인 2가 들어갈 것이다.
하지만 점화식의 개념으로 나아가 생각해보면, 다음과 같이 모든 값을 구할 필요 없이 이렇게 생각할 수도 있다.

DP[4] = DP[2] + 1
(DP[2]에서 * 2를 하면 되니, 카운트가 1 증가하였음.)

예를 들어 30의 최소값을 찾고자 한다면, 30의 경우 3으로도 나눌 수 있고, 2로도 나눌 수 있다.

10에서 3을 곱한 값과 15에서 2를 곱한 값, 그리고 29에서 1을 더한 값이라고 할 수 있다.
이는 DP[30] = DP[10] + 1 / DP[15] + 1 / DP[29] + 1로 표현할 수 있을 것이다. 이 값들 중 최소값을 찾아 저장하면 된다.

이를 활용하여 풀어보면 다음과 같다.

import java.util.*;
import java.io.*;


public class Main {
	final static int MAX = 1000000 + 1;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int X = Integer.parseInt(br.readLine());
		int[] DP = new int[MAX];
		
		DP[1] = 0; 
		DP[2] = DP[3] = 1;
		
		for (int i = 4; i < DP.length; i++) {
			if(i % 6 == 0) 
              DP[i] = Math.min(Math.min(DP[i - 1], DP[i / 3]), DP[i / 2]) + 1;
			else if(i % 3 == 0) DP[i] = Math.min(DP[i - 1], DP[i / 3]) + 1;
			else if(i % 2 == 0) DP[i] = Math.min(DP[i - 1], DP[i / 2]) + 1;
			else DP[i] = DP[i - 1] + 1;
			 
		}
		
		System.out.println(DP[X]);
		
	}
	
}