BOJ_S2_9184

📁 [S2_9184] 신나는 함수 실행

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static int[][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        dp = new int[21][21][21];

        while(true){
            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;
            }

            sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(w(a,b,c)).append("\n");

        }
        System.out.print(sb);

    }

    static int w(int a,int b,int c){

        // 이미 저장되있는 경우, 범위안에 있을 경우 바로 반환
        if(check(a,b,c) && dp[a][b][c] != 0){
            return dp[a][b][c];
        }

        // 재귀식 메모리제이션
        if(a <= 0 || b <=0 || c <= 0){
            return 1;
        }
        else if(a > 20 || b > 20 || c >20){
            return dp[20][20][20] = w(20,20,20);
        }
        else if(b > a && c > b){
            return dp[a][b][c] = w(a,b,c-1) + w(a, b-1, c-1) - w(a, b-1 ,c);
        }
        else{
            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);
        }
    }

    // 범위안에 있는지 확인
    static boolean check(int a, int b, int c){
        return a >=0 && a<=20 && b>=0 && b<=20 && c>=0 && c<=20;
    }
}

🤔 나의 생각

DP 문제이다.
기본적으로 재귀 함수의 구조는 나와있기 때문에 메모리제이션만 해주면 된다.
그러나 한 가지 더 해야할 것이 있었다. 바로 범위 설정이다.
a,b,c, 중 하나라도 20을 넘으면 그냥 재귀함수 w(20,20,20)을 불러오기 때문에
범위 안에 있거나 이미 메모리제이션 되어 있는 것은 바로 호출을 해주고
아닌 것들은 계속 메모리제이션 해가는 과정을 거친다.