[백준] 1174번 : 줄어드는 수 (C++)

1174번 : 줄어드는 수

---

 

문제)

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

 

 

 

입력 :

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

 

 

 

출력 :

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

 

 

 

 

 

풀이)

 

// 1174. 줄어드는 수
#include <iostream>
#include <queue>
#include <string>
 
using namespace std;
 
int n;
 
string bfs()
{
    // 수가 너무 커지기 때문에 string으로 다루어야 한다.
    queue<pair<string, int>> q;
    for (int i = 0; i < 10; i++)
    {
        q.push(make_pair(to_string(i), i));
    }
 
    int cnt = 1;
    while (!q.empty())
    {
        string a = q.front().first;
        int b = q.front().second;
        q.pop();
 
        if (cnt == n) return a;
        if (cnt > 1000000) break;
 
        for (int i = 0; i < b; i++)
        {
            q.push(make_pair(a + to_string(i), i));
        }
        cnt++;
    }
    
    return "-1";
}
 
int main()
{
    cin >> n;
 
    cout << bfs();
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/1174 

1174번: 줄어드는 수