BOJ)9184 신나는 함수 실행

문제: icpc.me/9184

문제에서 점화식 기저 까지 다 정해주는 진정한 꿀문제가 아닐까 싶다.

당연하게도 그냥 함수를 매번 계산한다면 시간초과가 난다.

하지만 우리는 점화식과 기저를 알고 있으니 이걸 이용해 다이나믹 프로그래밍을 이용하여 계산할때마다 결과를 배열에 저장해주면 된다.

문제에서 하라는대로 하면 쉽게 풀 수 있는 문제이다. 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[21][21][21];
int a, b, c;
int func(int x, int y, int z) {
    if (x <= 0 || y <= 0 || z <= 0)
        return 1;
    if (x > 20 || y > 20 || z > 20)
        return func(20, 20, 20);
    int &ret = dp[x][y][z];
    if (ret != -1)return ret;
    if (x < y&&y < z)
        return ret = func(x, y, z - 1) + func(x, y - 1, z - 1) - func(x, y - 1, z);
    return ret = func(x - 1, y, z) + func(x - 1, y - 1, z) + func(x - 1, y, z - 1) - func(x - 1, y - 1, z - 1);
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d%d", &a, &b, &c);
    while (!(a == -1 && b == -1 && c == -1)) {
        printf("w(%d, %d, %d) = %d\n", a, b, c, func(a, b, c));
        scanf("%d%d%d", &a, &b, &c);
    }
    return 0;
}