[백준 1038] 감소하는 수

작성일 | In |

문제 링크

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

풀이

과연 감수하는 수가 $N$의 상한인 $10^6$개나 있을 수 있을까요? 제일 큰 감소하는 수는 $9876543210$이고 이보다 작은 감소하는 수는 그리 많아 보이진 않습니다. 감소하는 수의 개수를 아무리 높게 잡는다고 해도 최대 $10^5$개라고 생각할 수 있고 이는 $O(N \log N)$이 충분히 통과할 만한 제한입니다. 모든 감소하는 수를 우선순위 큐에 넣고 작은 순서대로 뽑아낼 수 있지 않을까요? 처음 우선순위 큐에는 $[1,9]$구간 내의 수를 넣습니다. 우선순위 큐에 $N$번째 감소하는 수가 들어있지 않으면 우선순위 큐에 들어있는 가장 작은 수 $u$에 $[0,u\%10-1]$사이에 있는 숫자를 뒤에 붙여서 다시 우선순위 큐에 넣습니다. 이를 반복하다 보면 $N$번째 감소하는 수가 나오거나 우선순위 큐가 비어서 $N$번째 감소하는 수는 존재하지 않음을 알 수 있습니다.

추가로 우선순위 큐에 들어오는 수를 보면 수가 증가하는 순서대로 들어오기 때문에 우선순위 큐 대신 일반 큐를 이용한 구현이 가능합니다. 아래 코드는 큐를 이용한 구현입니다. 큐에 들어오는 수의 개수는 최대 $N$개 이므로 시간복잡도는 $O(N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
queue<ll> q;

int main(){
    scanf("%d",&n);
    if(n == 0) return !printf("0");

    for(int i=1;i<=9;i++) q.push(i);
    while(!q.empty() && --n){
        ll u = q.front(); q.pop();
        for(int i=0;i<u%10;i++) q.push(u*10 + i);
    }
    printf("%lld",q.empty() ? -1 : q.front());
}

여담

$9876543210$은 $1022$번째 감소하는 수입니다.