백준 2688 - 줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

 

각 자리의 숫자들이 단조 증가하는 수열을 구하는 문제이다.

1의 자리 숫자들은 문제에서 이야기하는 줄어들지 않음을 만족하므로 그 갯수를 1로 채우고 바텀업 DP를 통해 나머지 자리수들의 값을 채워나가면 된다.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[10][64];

int main()
{   
    for (int a = 0; a < 10; ++a)
        dp[a][0] = 1;
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    for (int i = 1; i < 64; ++i)
        for (int j = 0; j < 10; ++j)
            for (int k = j; k >= 0; --k)
                dp[j][i] += dp[k][i - 1];
    
    int t; cin >> t;
    
    while (t--)
    {
        ll res = 0;
        int digit;
        cin >> digit;
        
        for (int j = 0; j < 10; ++j)
            res += dp[j][digit - 1];
        cout << res << '\n';
    }
}