[알고리즘 문제] 백준1038 - 감소하는 수

 

www.acmicpc.net/problem/1038

1038번: 감소하는 수

문제는 bfs를 사용하여 해결할 수 있습니다. 743이라는 이후의 숫자는 마지막숫자보다 작은 숫자들, 7432,7431,7430이 올 수 있습니다. 그리고 arr[j]의 값은 j번째 숫자를 의미하며 que를 순회하면서 마지막 숫자에 그보다 작은 숫자들을 하나씩 붙여가면서 반복합니다.

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{

    int N;
    cin >> N;

    queue<long long> que;
    long long arr[1000001] = {0}; // j번째 숫자는 arr[j];

    if (N < 10)
    {
        cout << N << endl;
        return 0;
    }
    for (int i = 1; i <= 9; i++)
    {
        que.push(i);
        arr[i] = i;
    }

    int index = 9;

    while (index <= N)
    {
        if (que.empty())
        {
            break;
        }

        long long cur = que.front();
        que.pop();

        int tail = cur % 10;

        for (int i = 0; i < tail; i++)
        {
            que.push(cur * 10 + i);
            arr[++index] = cur * 10 + i;
        }
    }

    if (!arr[N])
    {
        cout << -1 << endl;
    }
    else
    {
        cout << arr[N] << endl;
    }

    return 0;
}