백준 1038 - 감소하는 수

C++

1038 번 - 감소하는 수

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 문제 출처

접근 방법

1. 가장 큰 감소하는 수는 9876543210이다. 그 이상의 값은 감소하는 수가 아니므로, 0부터 9876543210까지 수를 1씩 더하며 탐색을 한다.
2. 각 수를 string으로 변환하고 앞에서 부터 각자리의 수가 감수하는 지 확인하여 감수하는 수이면, n번째 감소하는 수로 저장한다.
3. 하지만 이는, 너무 많은 수를 확인하며 예를들어 100인 경우 199까지 감소하는 수가 될 수가 없으므로 210까지 건너띄어야 한다.
4. 탐색 도중 N번째의 수가 도달하면 반복을 중단한다.

구현

각 자리의 수를 비교하며 뒷자리가 감소하지 않으면 false를

코드

#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;
vector<long long> dcNum;
int n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    long long num = 0;
    int idx = 0, jump;
    bool chk = true;
    while (idx != n + 1 && num <= 9876543210) {
        string tempNum = to_string(num);
        for (int i = 0; i < tempNum.size() - 1; i++) {
            if (tempNum[i] - '0' <= tempNum[i + 1] - '0') {
                chk = false;
                //i의 자리 수 만큼 num을 더해주어, jump하게 만든다.
                jump = tempNum.size() - i - 1;
                num = num / pow(10, jump);
                num++;
                num = num * pow(10, jump);
                num--;
                break;
            }
        }
        if (chk) {
            dcNum.push_back(num);
            idx++;
        }
        chk = true;
        num++;
    }

    if (dcNum.size() < n + 1) {
        cout << -1;
    }
    else {
        cout << dcNum.at(n);
    }
}

후기 및 개선할 점