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

문제

백준 1038 감소하는 수 C++

1038번: 감소하는 수

풀이

감소하는 수의 순서는 다음과 같습니다.

한 자리 : 0 (0번째) -> 1 (1번째) ~ ... ~ 9 (9번째)

두 자리 : 10 -> 20 -> 21 -> 30 -> 31 -> 32 -> ... -> 98

세 자리 : 210 > 310 -> 320 -> 321 -> ... -> 987

네 자리 : 3210 -> ... -> 9876

...

열 자리 : 9876543210

각 자리 수가 0~9 이기 때문에 열 자리 이상의 감소하는 수는 존재할 수 없습니다.

숫자들을 보면 다음과 같은 패턴을 볼 수 있습니다.

(한 자리)

1 -> 0을 붙여 두 자리 감소하는 수 10을 만들 수 있습니다. (첫 번째 두 자리 감소하는 수)

2 -> 0 또는 1을 붙여 두 자리 감소하는 수 20, 21을 만들 수 있습니다. (두, 세 번째 두 자리 감소하는 수)

(두 자리)

10, 20 -> 0보다 작은 수는 없으므로 끝에 숫자를 붙여 세 자리 감소하는 수를 만들 수 없습니다.

21 -> 0을 붙여 세 자리 감소하는 수 210을 만들 수 있습니다. (첫 번째 세 자리 감소하는 수)

32 -> 0 또는 1을 붙여 세 자리 감소하는 수 320, 321을 만들 수 있습니다. (두, 세 번째 세 자리 감소하는 수)

 

이런 식으로 n 자리 수의 마지막 숫자보다 더 작은 숫자를 수 끝에 붙이는 방식으로 n+1 자리 수를 만들 수 있습니다.

따라서 queue를 pop 하고 push 해가며 감소하는 수를 구하고, vector에 push 해서 인덱스를 입력받으면 바로 출력할 수 있게 해 줍니다.

범위를 벗어난 입력(v의 크기보다 같거나 큰 수를 입력받은 경우)에는 -1을 출력합니다.

감소하는 수는 int범위를 초과하므로 자료형에 주의합시다.

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
 
vector<long long> v;
 
void fun(int target) {
    queue<long long> q;
    for (int i = 0; i <= 9; i++) {
        q.push(i);
        v.push_back(i);
    }
    while (!q.empty()) {
        long long num = q.front();
        // 맨 끝에서 가져오기
        int last = num % 10;
        q.pop();
        // 끝자리 보다 작은 수 뒤에 넣고 q에 push
        for (int i = 0; i < last; i++) {
            long long newnum = num * 10 + i;
            q.push(newnum);
            v.push_back(newnum);
        }
    }
    // 범위 초과
    if (target >= v.size()) {
        cout << -1;
    }
    else {
        cout << v[target];
    }
}
 
int main() {
    int N;
    cin >> N;
    fun(N);
    return 0;
}