126. 9184 (신나는 함수 실행)

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

class Main {
	static int[][][] memo;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		memo = new int[21][21][21];

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

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

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

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

		System.out.println(sb);
	}

	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) {
			return w(20, 20, 20);
		}

		if (memo[a][b][c] > 0) {
			return memo[a][b][c];
		}

		if (a < b && b < c) {
			memo[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
			return memo[a][b][c];
		}

		memo[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 memo[a][b][c];
	}

}

문제요약

재귀함수를 동적프로그래밍으로 바꾸는 문제

설명

동적프로그래밍을 알면 크게 어렵지 않다.

동적프로그래밍의 개념은 아래를 참고하자.

https://smhope.tistory.com/328?category=1056187 

동적프로그래밍(Dynamic Programming)

if (memo[a][b][c] > 0) {
			return memo[a][b][c];
		}

메모에 기입되있다면 넘어간다.