백준 1038번 감소하는 수

문제 링크입니다: https://www.acmicpc.net/problem/1038

분류는 DP 문제라고 되어있지만 간단하게 큐를 이용하여 풀었습니다.

기존에 감소하는 수라고 판별된 숫자를 큐에 집어넣어 마지막 자리숫자보다 작은 숫자들을 붙여나가는 방식으로 나열했습니다.

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 1000000;

 

int N;

int idx = 9; //1~9는 이미 감소수라고 여김

queue<long long> q;

long long descending[MAX + 1];

 

void preCalculate(void)

{

        while (idx <= N)

        {

                 if (q.empty())

                         return;

                 //큐에 있는 감소수를 꺼내서

                 long long descendingNum = q.front();

                 q.pop();

                 //마지막 자리 숫자를 확인

                 int lastNum = descendingNum % 10;

                 //마지막 자리 숫자보다 작은 숫자들을 붙여 나감

                 for (int i = 0; i < lastNum; i++)

                 {

                         q.push(descendingNum * 10 + i);

                         descending[++idx] = descendingNum * 10 + i;

                 }

        }

}

 

int main(void)

{

        cin >> N;

        //1~9는 이미 감소하는 수

        for (int i = 1; i <= 9; i++)

        {

                 q.push(i);

                 descending[i] = i;

        }

        preCalculate();

 

        //N이 범위를 초과했을 경우

        if (!descending[N] && N)

                 cout << -1 << endl;

        //정상적인 범위일 경우

        else

                 cout << descending[N] << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~