[ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184)

https://www.acmicpc.net/problem/9184

재귀를 DP로 바꾸는 문제이다 [실버2]

재귀 호출만 생각하면 신이 난다! 아닌가요?

 

 

아래와 같은 재귀 호출 알고리즘 코드가 있다

하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다

따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if (a == -1 && b == -1 && c == -1) {
                break;
            }

            System.out.println("w(" + a + ", " + b + ", " + c + ") = " + w(a, b, c));
        }
        br.close();
    }

    private static int w(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }
        if (a > 20 || b > 20 || c > 20) {
            return w(20, 20, 20);
        }

        if (a < b && b < c) {
            return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        }
        return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }
}

 

식을 DP로 바꾼다고 해서 위의 재귀호출 코드 원리를 다 이해할 필요는 없다. 아마 엄청나게 복잡할 것이다!

우리는 DP의 원리만 잘 이해하면 된다.

 

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

public class Main {
    private static int[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        dp = new int[21][21][21];
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if (a == -1 && b == -1 && c == -1) {
                break;
            }
            System.out.println("w(" + a + ", " + b + ", " + c + ") = " + w(a, b, c));
        }

        br.close();
    }

    private static int w(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }
        if (a > 20 || b > 20 || c > 20) {
            return dp[20][20][20] = w(20, 20, 20);
        }
        if (dp[a][b][c] != 0) { // dp[a][b][c] 값이 메모리에 저장해 둔 값이라면 바로 사용
            return dp[a][b][c];
        }

        // 메모리에 저장해 둔 값이 아닌 처음 만나는 값이라면 값을 저장하며, 더 깊숙하게 재귀
        if (a < b && b < c) {
            return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        }
        return dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }
}

 

변형한 코드는 다음과 같다. 3차원 배열 메모리를 사용해 DP를 구현하였다. 생각보다 엄청 쉽지 않은가?

속도도 굉장히 빠르다! 재귀호출로 깊게 안 들어가고, 그냥 이전의 결괏값을 활용해 바로 연산을 해버리니 속도가 빠른 것이다. 실제로 시간 복잡도는 단지 반복문 O(N) 뿐이며, 15 15 15 를 입력했을 때 전과 다르게 바로 결괏값이 출력되는 것을 알 수가 있다.

 

이처럼 DP는 굉장히 효율적인 알고리즘이기 때문에 잘 알아두어야 한다. 중복 계산이 많은 문제에서는 과장을 조금 보태서 "DP보다 빠른 방법은 없다" 단순 재귀나 브루트포스를 사용하면 지수 시간이 걸리지만, DP로 하면 주로 다항 시간에 해결이 가능하기 때문이다. 재귀 호출만 생각하면 신이 난다! 아닌가요?