[BOJ] 9184. 신나는 함수 실행

문제 원본 : https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

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

public class Main {
    public static int[][][] w = new int[101][101][101];

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

        int a, b, c;
        StringTokenizer st = null;
        StringBuilder builder = new StringBuilder();
        while (true) {
            String abc = br.readLine();

            if (abc.equals("-1 -1 -1")) {
                break;
            }

            st = new StringTokenizer(abc);
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            builder.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(W(a + 50, b + 50, c + 50)).append("\n");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }

    public static int W(int a, int b, int c) {
        if (w[a][b][c] > 0) {
            return w[a][b][c];
        }

        if (a <= 50 || b <= 50 || c <= 50) {
            return w[a][b][c] = 1;
        } else if (a > 70 || b > 70 || c > 70) {
            return w[a][b][c] = W(70, 70, 70);
        } else if (a < b && b < c) {
            return w[a][b][c] = W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c);
        } else {
            return w[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);
        }
    }
}

• 다이내믹 프로그래밍 문제
• 문제에서 주어진대로 memoization 하면서 재귀를 돌리면 풀린다.