문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

-50 ≤ a, b, c ≤ 50

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

풀이

해당 문제는 주어진 함수를 그대로 옮기면서 dp로 풀면된다. a,b,c에 대해 값이 저장되는 dp 테이블을 3차원으로 만들어서 풀면 쉽게 해결할 수 있다.

배열의 범위를 21로 한 이유는 함수 내에서 20이 넘어가면 w(20,20,20)을 하게되니 결국 20을 초과하는 범위는 나올 수 없는 것이다.

d[a][b][c] != 0 이라는 조건을 저 위치가 아니라 (a<b && b<c) 조건 다음으로 넣게되면 시간초과가 발생하니 유의해야한다.

다른사람의 풀이를 보면서 처음에 범위를 벗어나는지 체크를 하는데, 굳이 그럴 필요가 없는 이유는 0이하일 때와 20보다 클때를 먼저 체크를 해주기 때문에 할 필요가 없는 것이다.

소스

import java.io.*;

public class Main {
	public static int a, b, c;
	public static int[][][] d = new int[21][21][21];

	public 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 (d[a][b][c] != 0) {
			return d[a][b][c];
		}

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

		return d[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);

	}

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

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

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

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

		}
		br.close();

	}

}