[백준] 1038번 감소하는 수, 1174번 줄어드는 수

문제

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

출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1038)

문제 풀이

오르막 수와 비슷한 문제다. 그 문제는 dp를 통해서 N자리 수까지의 오르막 수를 구하는 거였는데 이 문제는 N번째 감소하는 수를 구해야한다. 처음에는 dp로 몇번째 자리수에 N번째 감소하는 수가 있는지를 찾은 다음 브루트포스를 통해서 해당하는 수를 찾으려고 했는데 시간초과를 줄이지 못했다. 다른 방법을 쓰면 생각보다 간단했는데 543이라는 감소하는 수가 있다면 맨 마지막 수보다 작은 숫자들을 붙여서 5431, 5432 와 같이 감소하는 수를 만들 수 있다. 감소하는 수가 있다면 큐에 넣고, 작은 수부터 빼서 맨 뒷자리에 붙여나가며 감소하는 수를 만들면 N번째 감소하는 수가 되었을 때 출력을 하면되고 감소하는 수가 아닌 불필요한 숫자를 제외한 N번의 탐색을 통해 구할 수 있다. 

좀 더 자세히 설명을 하면 처음에 1~9까지는 감소하는 수이고 차례대로 큐에 넣었을 것이다. 1이 pop되었을 때는 뒤에 0을 붙일 수 있으니 10을 큐에 넣게되고 2를 pop했을 때는 0과 1을 붙일 수 있으니 20, 21을 큐에 넣을 수 있다. 이렇게 큐를 사용하면 간단하게 해결할 수 있다! 

그리고 처음엔 N번째 감소하는 수가 없다면 -1을 출력하라는 말이 무엇인지 이해를 하지 못했었는데 생각해보니 9876543210 이후에는 감소하는 수를 만들 수 없다. 9876543210 은 1023번째 감소하는 수 이므로 1023 초과하는 N이 들어올 경우는 -1를 출력하도록 한다. 

이 방법 말고 jump 라는 변수를 통해서(dp+브루트포스에서 시간초과를 피하기 위해) 불필요한 숫자는 감소하는 수인지를 검사하지 않고 해결하는 방법으로 푼 사람이 많았는데 이 방법으로도 한번 더 풀어봐야겠다.

코드

#include<iostream>

#include<queue>

using namespace std;

queue<int> decrease;

int main(){

    

    int n;

    int cnt=0;

    int i, j, tmp;

    cin>>n; 

if(n <= 10){

cout<<n<<endl;

}

else if( n == 1022)

cout<<9876543210<<endl;

else if(n >= 1023)

cout<<"-1"<<endl;

else{

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

decrease.push(i);

cnt++;

}

while(cnt < n ){

i = decrease.front();

decrease.pop();

tmp = i%10;

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

decrease.push(i*10 + j);

cnt++;

if(cnt == n){

cout<<i*10 + j<<endl;

break;

}

}

}

}

return 0;

    

}