동적 계획법(Dynamic Programming)

동적 계획법이란?

"어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘이다.

 

다시 말하면

어떠한 문제를 풀 때, 이전의 문제를 기반으로 현재 문제를 해결해야하는 상황이 온다면 

똑같은 과거의 문제를 풀어야하는 상황에 노일 수도 있다.

 

예시로)

A라는 문제를 풀기위해 B라는 녀석을 풀었다.

근데 C라는 문제를 풀기위해 B라는 녀석을 풀어야한다네?

B를 굳이 다시 풀어야할까? 

이미 A를 풀때 B를 풀었다면 B의 값을 기억하고 C를 풀면된다.

 

다음 예시와 같이 문제를 해결하는 것이 동적 계획법 DP다. 

 

---

 

그렇다면 DP 를 구현하기 위해 어떻게 문제에 접근해야할까?

1. 상향식 접근방식
하위 문제에 대한 결과 계산을 시작한다 . 하위 문제 결과를 사용하여 다른 하위 문제를 해결하고

마지막으로 전체 문제를 해결한다.

예
피보나치 수열의 n번째 멤버를 찾아보자.

피보나치(0) = 0

피보나치(1) = 1

피보나치(2) = 1(피보나치(0) + 피보나치(1)

피보나치(3) = 2(피보나치(1) + 피보나치(2)

우리는 그 문제를 차근차근 해결할 수 있다

1. t 번째 멤버 찾기를 위한 식

2. 첫 번째 멤버 찾기

3. 0번째와 1번째 멤버를 사용하여 2번째 멤버를 계산한다.

4. 첫 번째와 두 번째 멤버를 사용하여 세 번째 멤버를 계산한다.

 

계속해서 t 번쨰 맴버를 찾는다. 그러나 이러한 연산 중에 중복이 발생한다. 

 

                      Fib(4)
                     /    \
                Fib(3)    Fib(2)
               /     \     /   \
          Fib(2)  Fib(1) Fib(1)  Fib(0)
         /    \
    Fib(1) Fib(0)

이렇게 fib(0) 이 두번 fib(1)이 3번  fib(2)가 2번 계산됐다. 

비효율적인 계산이 일어난 것이다. 

그렇기에 계산 후 해당 값을 저장하면 다음과 같은 중복을 예방할 수 있다. 

---

위에 예시를 통해 피보나치 수열의 계산에서 값을 기억하기로 했다.

그럼 이번에는 아래 문제를 통해 연산을 한 값을 기억하며 큰 문제로 접근해보자. 

1463번: 1로 만들기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	static Integer[] dp;
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;
 
		System.out.print(recur(N));
 
	}
 
	static int recur(int N) {
 
		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}
 
}