BOJ 1038 감소하는 수

백준 1038 링크

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

1038번: 감소하는 수

풀이

처음엔 DP를 이용하여 규칙성을 발견해서 풀려고 시도해 특정 구간까지 DP로 도달해서 브루트포스로 도달하는 방법을 시도해 보았지만 시간초과가 났고, 생각하던중 큐를 이용하여 푸는 방법을 생각해 내서 풀었음.

 

예를 들어 763이라는 수를 큐에서 꺼냈으면 다시 큐에다 7630, 7631, 7632를 넣는 식으로 풀었다.

 

가장 마지막수는 오버플로우가 나서 따로 출력해 주었음.

코드

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

int main() {
	//freopen("input.txt","r",stdin);
	
	int count, input, now_value;
	queue <int> q;
	count = 0;
	cin>>input;
	
	for(int i=0;i<10;i++){
		q.push(i);
	}
	
	if(input == 1022){
		cout<<9876543210;
		return 0;
	}
	else if(input>1022){
		cout<<-1;
		return 0;
	}
	
	while(1){
		now_value = q.front();
		q.pop();
		if(count++ == input){
			cout << now_value;
			break;
		}
		for(int i = 0; i < now_value%10; i++){
			q.push(now_value*10 + i);
		}
	}
}