BOJ 2688 : 줄어들지 않아

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

2688번: 줄어들지 않아

그냥 누가 봐도 DP로 전처리를 하고 각 입력에 대응하면 된다.

dp[i][j] = "길이가 i, 마지막 자리의 수가 j일 때 경우의 수"

경우를 따져 보자.

 

1번째 경우 : i=1일 때 

dp[i][j] = 1

 

2번째 경우 : i>1일 때

dp[i][j] = Σ dp[i-1][k] (0<=k<=j)

 

#include <bits/stdc++.h>
#define MEM 66
#define sanic ios_base::sync_with_stdio(0)
#define f first
#define s second
#define pb push_back
#define all(x) ((x).begin()),((x).end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll dp[MEM][MEM];
ll t,n;
int main() {
    sanic; cin.tie(0);
    for(int i=1; i<65; i++){
        for(int j=0; j<10; j++){
            if(i==1) dp[i][j] = 1;
            else
                for(int k=0; k<=j; k++)
                    dp[i][j] += dp[i-1][k];
        }
    }
    cin >> t;
    while(t--){
        cin >> n;
        ll ans=0;
        for(int i=0; i<10; i++)
            ans += dp[n][i];
        cout << ans << '\n';
    }
}