백준 1038 감소하는 수

https://www.acmicpc.net/problem/1038

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 숫자가 첫번째 자리수부터 순서대로 감소하는 N번째 숫자를 찾는 문제입니다. 1000000번째 숫자까지 입력이 가능하므로 단순히 각 자리수를 차례대로 비교하면서 찾는 방법으로는 시간초과가 나게 됩니다. 그래서 불필요한 탐색을 줄일 수 있는 방법은 더큰 감소하는 수는 작은 감소하는 수에 숫자를 덧붙이면 만들어 진다는 것을 알 수 있습니다. 따라서 큐에 0~9는 기본적으로 감소하는 수이므로 넣어주고 각각 숫자들로 만들 수 있는 감소하는 수를 넣어주고 다 만든 숫자는 pop해주면서 N번째 숫자를 찾았습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	queue <long long> q;
	int num = -1;
	bool flag = true;
	
	for(int i = 0; i < 10; i++) {
		q.push(i);
		num++;
		if(N == num)
			break;
	}
	
	
	 
	while(1) {
		int len = q.front() % 10;
		if(q.front() < 10) { //감소하는 수에 10을 곱하고 끝자리에 숫자를 더해서 새로운 감소하는 수를 만듬 
			for(int i = 0; i < q.front(); i++) {
			if(N == num)
				break;
			q.push(q.front()*10+i);
			num++;
		}
		q.pop();
		}
		else {
		for(int i = 0; i < len; i++) {
			if(N == num)
				break;
			q.push(q.front()*10+i);
			num++;
		}
		q.pop();
	}
		if(q.back() == 9876543210 && N!=num) { //범위를 초과하면 flag 를 false로 
			flag = false;
			break;
		}
		if(N == num)
			break;
	}
	if(flag)
		cout<<q.back();
	else
		cout << -1;
	
}