[백준] 감소하는 수

문제

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

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 1 복사

18

예제 출력 1 복사

42

---

예전에 감소하는 수가 아닌 증가하는 수? 비슷한 문제에선 dp로 해결했던 게 기억이 나서 일일이 증가하며 풀려다가 말았다. 감소하는 수는 큐를 이용해서 x수의 끝에 끝자리보다 작은 수를 더하면서 푼다.

예를들어 853가 있을때 이 수의 뒤에 0,1,2를 붙여서 다음 수를 만드는 것이다. 

전역변수 idx와 bfs를 이용해 해결했다.

가장 큰 수는 9876543210으로 int 범위를 넘기 때문에 long long을 쓰자

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EA%B0%90%EC%86%8C%ED%95%98%EB%8A%94%20%EC%88%98(1038%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
long long p[1000001]; // i번째 감소하는 수
int N, idx = 10;
queue<long long> q;

void bfs()
{
	while (!q.empty()) {
		long long cur = q.front();
		q.pop();
		int last = cur % 10;
		for (int i = 0; i < last; i++) {
			q.push((long long)cur * 10 + i);
			p[idx++] = (long long)cur * 10 + i;
		}
	}
}

int main()
{
	cin >> N;
	for (int i = 1; i < 10; i++) {
		q.push(i);
		p[i] = i;
	}

	bfs();
	
	if (p[N] == 0 && N != 0)
		cout << -1;
	else
		cout << p[N];

}