백준 9184번 신나는 함수 실행

주어진 재귀함수를 실제로 구현하는 문제다.

 

동적프로그래밍을 활용할 경우, 값을 저장할 배열(DP 라고 하겠다)의 사이즈를 고민해볼 필요가 있다.

 

문제의 제한 사항에서 a, b, c의 범위가 주어졌지만, 주어진 재귀함수의 첫 번째와 두 번째 조건

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

에 의해 DP의 사이즈는 [21][21][21] 로 선언할 수 있다.

 

import java.util.Scanner;

public class Main {

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

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        while (true) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();

            if (a == -1 && b == -1 && c == -1) {
                break;
            }

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

        }

    }

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

        if (inRange(a, b, c) && dp[a][b][c] != 0) {
            return dp[a][b][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 (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);
    }
    
    static boolean inRange(int a, int b, int c) {
        return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20;
    }
}