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

문제

BOJ 9184. 신나는 함수 실행

풀이

문제는 신이 난다고 하지만 정작 문제를 풀어야하는 나는 신나지 않은 문제..
피보나치 함수를 풀 때 처럼 효율을 고려하여 BufferedReader + StringBuilder로 풀었지만 Scanner나 sysout을 사용해도 풀리긴한다!
w(a,b,c) 함수는 문제에서 주어지기 때문에 이를 DP로 풀어나가기만 하면 됐다.
3 개의 변수를 다루기 위해 3차원 배열을 이용했다.
주어지는 입력은 -50 <= a, b, c <= 50 이였지만 실제로 사용되는 범위는 0 <= a, b, c <= 20이라서 int[21][21][21]로 크기를 할당했다! 처음 방문한 경우엔 재귀를 통해 계산 후 저장해주고, 이미 방문한 경우에는 DP[a][b][c]에 담긴 값을 그대로 재사용해서 풀었다.

JAVA코드

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

public class 백준9184_신나는함수실행 {
	static int[][][] DP = new int[21][21][21];

	public static void main(String[] args) throws IOException {

		DP[0][0][0] = 1;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		;
		StringBuilder sb = new StringBuilder();
		int cnt = 0;
		StringTokenizer st;
		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;

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

		}

		System.out.print(sb);

	}

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

		if (a <= 0 || b <= 0 || c <= 0) {
			return DP[0][0][0];
		}
		
		if (a > 20 || b > 20 || c > 20) {

			if (DP[20][20][20] == 0) {
				DP[20][20][20] = w(20, 20, 20);
			}

			return DP[20][20][20];
		}

		if (DP[a][b][c] == 0) {
			if (a < b && b < c) {

				DP[a][b][c - 1] = w(a, b, c - 1);
				DP[a][b - 1][c - 1] = w(a, b - 1, c - 1);
				DP[a][b - 1][c] = w(a, b - 1, c);

				return DP[a][b][c - 1] + DP[a][b - 1][c - 1] - DP[a][b - 1][c];
			} else {

				DP[a - 1][b][c] = w(a - 1, b, c);
				DP[a - 1][b - 1][c] = w(a - 1, b - 1, c);
				DP[a - 1][b][c - 1] = w(a - 1, b, c - 1);
				DP[a - 1][b - 1][c - 1] = w(a - 1, b - 1, c - 1);
				return DP[a - 1][b][c] + DP[a - 1][b - 1][c] + DP[a - 1][b][c - 1] - DP[a - 1][b - 1][c - 1];
			}
		}

		return DP[a][b][c];
	}

}