<백준> 9184

신나는 함수 실행

문제

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

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

그저 나온 대로만 코드를 짜면 시간 초과가 나온다.
그렇기에 어떻게 풀어야할까 고민했는데 이미 방문한 곳은 다시 방문 하지 않도록 코드를 추가했더니 정답이었다.

int dp[21][21][21];

int recur(int a, int b, int c)
{
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;
	if (a > 20 || b > 20 || c > 20)
		return recur(20, 20, 20);
	if (dp[a][b][c] != 0)
		return dp[a][b][c];
	dp[a][b][c] = recur(a - 1, b, c) + recur(a - 1, b - 1, c) + recur(a - 1, b, c - 1) - recur(a - 1, b - 1, c - 1);
	return dp[a][b][c];
}

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

	int a, b, c;
	while (1)
	{		
		cin >> a >> b >> c;

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

		cout << "w(" << a << ", " << b << ", " << c << ") = " << recur(a, b, c) << "\n";
	}
}