[백준 1038] 감소하는 수, C++

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

1038번: 감소하는 수

 본 문제는 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소하면 X를 감소하는 수라고 한다. 예) 321, 950 입력의 크기가 1,000,000 보자 작거나 같을 때, N번째 감소하는 수를 출력하시오, 단, 0은 0번째 감소하는 수, 1은 1번째 감소하는 수이며, N번째 감소하는 수가 없다면 -1을 출력해라.

이번 해설은 맞을 때까지 고민한 방법에 대해 나열했다. 이유 없다. 그냥 그러고 싶다.

1. 문제를 접했을 때, 최대 크기를 생각 안 하고 0부터 N까지 감소하는 수를 검사하면서 찾았다. 물론 시간 초과를 받았다.

#include <cstdio>
#include <string>
 
using namespace std;
 
int d[1000001];
 
bool chk(int x) {
    string s = to_string(x);
    if (s.size() == 1) return true;
    for (int i = 0; i < s.size()-1; i++) {
        if ( (s[i] - '0') <= (s[i+1] - '0') ) return false;
    }
    return true;
}
 
int main() {
    int n;
    scanf("%d", &n);
    int x = 0;
    int num = 0;
    while (num <= n) {
        if (chk(x)) {
            d[num] = x;
            num += 1;
        }
        x += 1;
    }
    printf("%d\n", d[n]);
}

 

2. 문자열을 이용하여 마지막 숫자보다 작은 수만 더해서 변환하자는 생각으로 코딩을 하였다. 결과는 틀렸습니다.

#include <cstdio>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v;
    for (int i = 0; i <= 9; i++) {
        v.push_back(i);
    }
    int start = 0;
    while (v.size() < n) {
        int end = v.size();
        for (int i = start; i < end; i++) {
            string tmp = to_string(v[i]);
            int ans = stoi(tmp);
            for (int j = 0; j < tmp[tmp.size()-1]-'0'; j++) {
                v.push_back((ans*10)+j);
            }
        }
        start = end;
    } 
    printf("%d\n", v[n]);
}

4. 생각해보니 마지막 자릿수는 %10의 결과와 같다. 또 잘은 모르겠지만 vector의 크기를 계산하면서 반복하는 것은 효율이 안 좋을 거 같다. 배열을 이용해서 풀자 그리고 감소하는 수열이 없을 경우 -1 출력하자 결과는 맞았습니다!

#include <cstdio>
 
using namespace std;
 
long long d[1000001];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= 9; i++) {
        d[i] = i;
    }
    int num = 10;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (d[i]%10); j++) {
            d[num++] = d[i]*10 + j;
        }
    }
    if (n > 1022) printf("-1\n");
    else printf("%lld\n", d[n]);
}