백준 9184 : 신나는 함수 실행

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

이미 연산했던 결과는 메모이제이션 해줍니다.

입력되는 값의 범위는 -50 이상 50 이하이지만,

하나라도 0 미만이거나 20 초과일 경우 1 또는 w(20, 20, 20)을 리턴하므로,

dp[0~20][0~20][0~20]인 값만 기억해두면 됩니다.

​

 

#include <cstdio>

int dp[21][21][21] = { 0 };

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 dp[20][20][20] = w(20, 20, 20);
	int& ret = dp[a][b][c];
	if (ret != 0) return ret;
	if (a < b && b < c) return ret = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	return ret = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}

int main() {
	int a, b, c;
	while (1) {
		scanf("%d %d %d", &a, &b, &c);
		if (a == -1 && b == -1 && c == -1) break;
		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
	}
}