본문 바로가기

알고리즘 관련/BOJ

BOJ)2688 줄어들지 않아

문제: icpc.me/2688


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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 < || 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, -1sizeof(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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2157 여행  (0) 2017.04.05
BOJ)2618 경찰차  (2) 2017.04.05
BOJ)2230 수 고르기  (0) 2017.04.04
BOJ)9463 순열 그래프  (1) 2017.04.03
BOJ)2992 크면서 작은 수  (0) 2017.04.03