1038 감소하는 수

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

d[i][j] = i자리이면서 오른쪽 끝자리가 j인 감소하는 수의 개수 라고 하자. 그러면 d[i][j]는 하나 작은 자리수이면서 끝자리가 j보다 큰 수들에다가 j를 붙이면 된다. 따라서 d[i][j] += d[i-1][k] (j+1<=k<10) 이다. DP로 미리 자리수마다 개수를 세어주고 n번째 감소하는 수가 속하는 자리수를 찾는다. 그 다음 경우의 수를 만들어서 정답을 찾는다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int n,i,j,k,d[11][10],cnt[11];
 
int main()
{
    scanf("%d",&n);
    if(n>1022)
    {
        printf("-1\n");
        return 0;
    }
 
    for(j=0;j<10;j++)
        d[1][j]=1,cnt[1]++;
    for(i=2;i<11;i++) for(j=0;j<10;j++) for(k=j+1;k<10;k++)
        d[i][j]+=d[i-1][k],cnt[i]+=d[i-1][k];
    for(i=2;i<11;i++)
        cnt[i]+=cnt[i-1];
 
    int digit,m;
    for(i=1;i<11;i++)
    {
        if(n<=cnt[i])
        {
            if(n==cnt[i]) m=0,digit=i+1;
            else m=n-cnt[i-1],digit=i;
            break;
        }
    }
 
    string p;
    for(i=0;i<10;i++)
        p.push_back(i<digit?'1':'0');
    vector<string> v;
    do v.push_back(p); while(prev_permutation(p.begin(),p.end()));
    sort(v.begin(),v.end());
    for(i=0,j=9;i<10;i++,j--)
        if(v[m][i]=='1') cout<<j;
    cout<<'\n';
 
    return 0;
}