[1038] 감소하는 수

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

1038번: 감소하는 수

풀이가 꽤 다양하다. 

10자리, 9자리만 하드코딩하고 브루트포스하는 방법,

한자리 수를 넣고 뒤에 하나씩 이어붙이며 bfs하는 방법,

2차원 dp, 백트래킹 등이 가능한것으로 보인다.

---

#include <stdio.h>

#include <string.h>

#include <cmath>

using namespace std;

int dp[12][12];

int f(unsigned long long n) {

    int a[15] = {0};

    int i = 0, j;

    while (n) {

        a[i] = n % 10;

        n /= 10;

        i++;

    }

    for (j = 0; j < i - 1; j++) {

        if (a[j + 1] - a[j] > 0) {

        } else {

            return false;

        }

    }

    return true;

}

int main(void) {

    int n, i, j, k, temp, num = 10, key = 0, x;

    scanf("%d", &n);

    if (n == 1022) {

        printf("9876543210");

        return 0;

    } else if (n > 1022) {

        printf("-1");

        return 0;

    }

    for (i = 0; i <= 9; i++) dp[1][i] = 1;

    for (i = 2; i <= 10; i++) {

        for (j = 0; j <= 9; j++) {

            temp = 0;

            for (k = 0; k <= j - 1; k++) temp += dp[i - 1][k];

            dp[i][j] = temp;

            num += temp;

            if (num >= n) {

                key = 1;

                break;

            }

        }

        if (key == 1) break;

    }

    x = (j + 1) * pow(10, (i - 1)) - 1;

    for (; num != n; x--) {

        if (f(x)) {

            num--;

        }

    }

    printf("%d", x + 1);

    return 0;

}

---