BOJ)2688 줄어들지 않아

문제: icpc.me/2688

N자리 줄어들지 않는 숫자를 구하는 문제이다.

dp테이블을 dp[pos][val]을 val로 끝나는 pos자리 줄어들지 않는 숫자의 수로 정의한 뒤 다이나믹 프로그래밍을 통하여 해결할 수 있다.

long long을 사용하지 않는다면 overflow가 발생할 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll t, dp[100][10], n;
ll func(ll pos,ll val) {
    if (val < 0 || val>9)return 0;
    if (pos == 1)return 1;
    ll &ret = dp[pos][val];
    if (ret != -1)return ret;
    ret = 0;
    for (int i = 0; i <= val; i++)
        ret += func(pos - 1, i);
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld", &n);
        ll res = 0;
        for (int i = 0; i < 10; i++)
            res += func(n, i);
        printf("%lld\n", res);
    }
    return 0;
}