1038 감소하는 수, 1174 줄어드는 숫자

1038 감소하는 수 https://www.acmicpc.net/problem/1038
1174 줄어드는 숫자 https://www.acmicpc.net/problem/1174

음이아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 줄어드는 숫자이다.
N번째 줄어드는 숫자(감소하는 수)를 구하는 문제다.

옛날에 풀었을 때는 못풀었던 문제다.

dp로 쉽게 점화식을 구해서 구할 수 있다.
$dp[s][l]$ : 앞자리가 $s$이면서 길이가 $l$인 줄어드는 수의 갯수
$dp[s][l]$ = $dp[s-1][l] + dp[s-1][l-1]$
앞자리가 $s$이면서 길이가 $l$인 가장 첫번째 줄어드는 수의 index 위치를 저장해놓으면
N번째 줄어드는 수를 구할 수 있다.

#include <iostream> #include <string> #include <algorithm> #include <map> using namespace std; int N; int cnt; int dp[10][11]; map<int, string> save; map<pair<int, int>, int> pos; int main() {     ios::sync_with_stdio(false);     cin >> N;     if (N > 1022) { cout << "-1\n"; return 0; }     for (int s = 0;s < 10;s++) save[++cnt] = to_string(s), pos[{s, 1}] = cnt, dp[s][1] = 1;     for (int l = 2;l < 11;l++) {         for (int s = l - 1;s < 10;s++) {             pos[{s, l}] = cnt + 1;             dp[s][l] = dp[s - 1][l] + dp[s - 1][l - 1];             int get = pos[{l -2, l - 1}];             for (int n = 0;n < dp[s][l];n++) {                 save[++cnt] = to_string(s) + save[get + n];             }         }     }     cout << save[N + 1];     return 0; } Colored by Color Scripter

cs