백준 1038번 : 감소하는 수

  정말 오랜만에 써보는 queue다. 맨날 DP문제 할 때 DFS밖에 안썼는데 갑자기 queue를 쓰려고 하니까 q.pop()이 queue에서 빼내면서 return해주는 건줄 알고 있었다.... 아마 제일 최근에 queue를 썼을 때가 파이썬이여서 그렇게 기억하고 있었나보다...ㅋㅋ

 

  인터넷에 있는 풀이는 몇가지가 있는데 나는 brute force는 괜히 복잡하고 맘에 안들어서 queue를 사용하는 방식을 택했다. 그래도 코드가 좀 더러워서 맘에 안들긴 하지만...ㅋㅋㅋ

 

  기본 개념은 이거다. 85는 감소하는 수다. 85뒤에 5보다 작은 수를 붙이면 그 수 역시 감소하는 수다. 854, 853, 852, 851, 850과 같이 말이다. 그래서 queue에 한자리수짜리 감소하는 수를 모두 넣어둔다. (사실 한자리 수는 그냥 모두 감소하는 수다.)

• queue = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

 

그리고 앞에서부터 빼면서 일의 자리의 수보다 작은 수들을 붙여서 다시 queue에 삽입해준다.

• queue = { 2, 3, 4, 5, 6, 7, 8, 9, 10 }
• queue = { 3, 4, 5, 6, 7, 8, 9, 10, 20, 21 }
• queue = { 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 }

 

  이런 식으로 말이다. 그러면 크기 순서를 지키면서 하나 하나씩 감소하는 숫자를 만들어나갈 수 있다. 감소하는 수를 만드는 것 자체는 DP를 많이 해봐서 기존의 감소하는 수의 제일 뒤에 숫자를 붙이면 되겠구나라고 금방 알았지만 크기 순서대로 수를 정렬시키기 위해 수들을 queue에 넣어서 관리해야겠다는 생각을 하기가 어려웠던 것 같다.

 

  아 그리고 처음에 n을 입력받을 때 왜 0, 1022, 1023보다 큰지 체크하냐면 위 알고리즘대로라면 0번째 감소하는 수가 0이라는 사실을 출력할 수 없었고 (지금 생각해보니 처음에 queue에 0부터 넣으면 될 것 같긴하다) 1022번째 숫자가 9876543210인데 아무래도 int의 범위를 벗어나는 것 같아서 저녀석만을 위해 int를 버리기 싫어서 따로 해줬다. 그리고 처음에 문제에서 왜 n번째 숫자를 출력할 수 없으면 -1을 출력하라고 했는지 몰랐는데 생각해보니 감소하는 최대 숫자는 9876543210이다! 이게 1022번째 숫자이고 이 이후로는 더 이상 해당하는 숫자를 만들 수 없기 때문에 n을 입력 받는 시점에서 미리 걸렀다.

 

#include <iostream>
#include <queue>

using namespace std;

int n;
queue<int> q;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    if(n == 0)
    {
        cout << "0";
        return 0;
    }
    else if(n == 1022)
    {
        cout << "9876543210";
        return 0;
    }
    else if(n >= 1023)
    {
        cout << "-1";
        return 0;
    }
    
    for(int i = 1; i <= 9; i++)
    {
        q.push(i);
    }
    
    while(!q.empty())
    {
        int num = q.front();
        q.pop();
        n -= 1;
        if(n == 0)
        {
            cout << num;
            break;
        }
        
        int last = num % 10;
        for(int i = 0; i < last; i++)
        {
            q.push(num * 10 + i);
        }
    }
 
    return 0;
}