[백준 9184] 신나는 함수 실행 (C++)

문제

---

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

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

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

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

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

 

입력

---

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

 

출력

---

 

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

 

제한

---

• -50 ≤ a, b, c ≤ 50

 

문제 풀이

---

dp 문제.

w 함수가 a, b, c 3개의 매개변수로 이루어져 있으므로 3차 dp 배열을 생성한다. 각 수의 범위는 -50부터 50까지이지만 어느 하나라도 0 이하의 수라면 1이고, 어느 하나라도 20 이상이면 w(20, 20, 20)이므로 각 수에 대해 0부터 20까지의 수만 표현해도 된다.

w 함수의 정의에 따라 a < b이고 b < c이면 dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k]이고, 아니라면 dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] - dp[i - 1][j - 1][k - 1]로 채워준다.

입력 값에 따라 어느 하나라도 0 이하라면 1을 출력하도록 하고, 어느 하나라도 20 이상이라면 dp[20][20][20]을 출력하게 하고, 그 외의 값에는 dp[a][b][c]를 출력하도록 한다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int*** dp = new int**[21];
	int a, b, c;
	for (int i = 0; i < 21; i++)
	{
		dp[i] = new int* [21];
		for (int j = 0; j < 21; j++)
		{
			dp[i][j] = new int[21];
			for (int k = 0; k < 21; k++)
			{
				dp[i][j][k] = 1;
			}
		}
	}
	for (int i = 1; i < 21; i++)
	{
		for (int j = 1; j < 21; j++)
		{
			for (int k = 1; k < 21; k++)
			{
				if (i < j && j < k)
				{
					dp[i][j][k] = dp[i][j][k-1]+ dp[i][j-1][k-1]-dp[i][j-1][k];
				}
				else
				{
					dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j - 1][k] + dp[i - 1][j][k-1] - dp[i-1][j-1][k-1];
				}
			}
		}
	}
	while (true)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)
		{
			break;
		}
		else
		{
			int answer = 0;
			if (a <= 0 || b <= 0 || c <= 0)
			{
				answer = 1;
			}
			else if (a > 20 || b > 20 || c > 20)
			{
				answer = dp[20][20][20];
			}
			else
			{
				answer = dp[a][b][c];
			}
			cout << "w(" << a << ", " << b << ", " << c << ") = " << answer << "\n";
		}
	}
	return 0;
}