DP. 신나는 함수 실행

문제

재귀가 반복되는 코드를 메모이제이션으로 실행시간을 대폭 단축시킬수있는 문제.

해결방향성

저장해논값을 그대로 재사용하는 메모이제이션을 직접 사용해본다. 개념으로만 봐서는 어떻게 사용하는건지 모른다.

코드

package dp;

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class FunnyFunction {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    /*public static int[][][] dpPlus = new int[50][50][50]; // 1 ~ 50
    public static int[][][] dpMinus = new int[51][51][51]; // -50 ~ 0*/
    public static int[][][] dp = new int[21][21][21];
    // -50~0 -> 안구해도됨. 그냥 1. 1~50 -> 근데 21부터 50까지는 w(20,20,20)이므로 안구해도됨.
    // 1~20까지만
    public static void main(String[] args) throws IOException{
        dp[0][0][0] = 1;

        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;
            }
            bw.write("w("+ a + ", "+ b + ", "+ c + ") = " + String.valueOf(w(a, b, c)) + "\n");

        }


        bw.flush();
        br.close();
        bw.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){ // 20보다 큰건 여기서 걸러짐.
            return w(20, 20, 20);
        }

        // Memoization : 메모이제이션 사용... -> 이미 계산한건 재귀로 돌리지않고 출력한다
        if (dp[a][b][c] != 0) {
            return dp[a][b][c];
        }
        if (a < b && b < c){ // 1이상 20이하인, a < b < c 인 경우만 계산해보자.
            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];
        }
        // 대소관계가 적용되지않는 1이상 20이하인 수들.

        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);
        return dp[a][b][c];

    }
}

/**
 * public static int w(int a, int b, int c) throws IOException{
 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 - 1, c - 1);
 }**/

결론

메모이제이션은 그냥 말그대로 꺼내는거였다.

if (dp[a][b][c] != 0) // dp[a][b][c]에 해당하는 값이 이미 입력되어있으면
{
	return dp[a][b][c]
}

참으로 쉽고 간단한 코드였다. 이 하나로 실행시간이 그렇게 많이 차이나다니 재귀를 한방에 날려버리는 코드.

• 사실 문제 자체도 이해하면 어렵지 않은 문제였다.
  예시에서 첫번째 줄에, 0을 포함한 음수들을 미리 걸러내고, 두번째 줄에, 21 이상의 수들을 미리 걸러내면, dp 배열에 1~20까지의 수들밖에 남지않는다.
  이걸 왜 처음에 보지못했을까. 조건문의 의미를 다시 새겨보는 문제였다.