[BOJ/백준][Gold5] 2688 : 줄어들지 않아 (C++)

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

2688번: 줄어들지 않아

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : 자리수가 n이면서 m으로 시작하는 수의 개수

 

#include <cstdio>
int t,N;
long long a[65][10];
int main(){
    scanf("%d",&t);
    for(int i=0;i<10;i++) a[1][i]=1;
    for(int i=2;i<65;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<=j;k++) 
                a[i][j]+=a[i-1][k];
    while(t--){
        scanf("%d",&N);
        long long ans=0;
        for(int i=0;i<10;i++) ans+=a[N][i];
        printf("%lld\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2688.cpp