Calm Dawn Studio

9184번 - 신나는 함수 실행 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int[][][] dp = new int[51][51][51]; // dp값을 저장할 배열 선언

	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 = 0, b = 0, c = 0;

		while (true) {

			String[] inputs = br.readLine().split(" ");
			a = Integer.parseInt(inputs[0]);
			b = Integer.parseInt(inputs[1]);
			c = Integer.parseInt(inputs[2]);

			if (a == -1 && b == -1 && c == -1) { // a = b = c = -1일 경우 반복문 탈출
				break;
			}

			int result = w(a, b, c);

			StringBuilder sb = new StringBuilder();
			sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(result);

			bw.write(sb.toString());
			bw.newLine();
		}

		bw.flush();
		bw.close();

	}

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

		if (dp[a][b][c] != 0) {
			return dp[a][b][c];
		}

		if (a > 20 || b > 20 || c > 20) {
			return 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);
	}

}

정답을 맞춘 풀이방법

1. DP문제로 재귀적인 방법을 사용하기 위해 미리 배열을 선언함

2. DP[][][]배열에 w함수를 실행하고 이때 이미 계산한 DP값이 존재할경우 값을 반환한다.

전형적인 DP문제로 Bottom-up 방식으로 자주 풀다보니 재귀적 방법은 다소 어려웠음ㅠㅠ