[백준] No. 1038 - 감소하는 수 (C++)

문제

www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

풀이

 쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 9,876,543,210로 int형의 최댓값인  2,147,483,647보다 크기 때문에 int 형이 아닌 long형을 써주지 않아 그런것 같다.

 

본인의 경우에는 감소하는 수가 0~9까지만 이용가능 하므로, 11자리 이상 갈 일이 없다고 생각하질 않고 문제를 풀어 메모리 초과가 발생했다...

 

두 점만 명심하고 풀면 어렵진 않다.

 

 

FindDescendNumber(int cnt)를 재귀호출 하며 cnt로 현재 생성할 수의 자릿수를 넘겨준다.

 

vector<long long> descendNumberSet 에 생성한 감소 하는 수를 저장하여 중복되는 계산을 없애준다.

 

for문을 돌며 i의 값이 descendNumberSet의 가장 높은 자릿수보다 클경우에만 해당 값이 감소하는 값이다.

 

 

코드

	#include<iostream>
	#include<vector>
	#include<cmath>
	using namespace std;
	int N;
	int countDescendNum=9;
	vector<long long> descendNumberSet;
	void FindDescendNumber(int cnt){
	vector<long long>::iterator iter;
	vector<long long> temp;
	long long powNum = pow(10,cnt-1);
	for(int i=1; i<10 ; ++i)
	for(iter = descendNumberSet.begin(); iter<descendNumberSet.end() ;++iter ){
	if(*iter%10 < i){
	temp.push_back(powNum*i + *iter);
	++countDescendNum;
	if(countDescendNum == N){
	cout<< powNum*i + *iter<<'\n';
	return;
	}
	}
	}
	descendNumberSet = temp;
	temp.clear();
	if(cnt<=10)
	FindDescendNumber(cnt+1);
	else
	cout<<-1<<'\n';
	}
	int main(){
	cin>>N;
	vector<long long> nextDescNumSet ={0,1,2,3,4,5,6,7,8,9};
	descendNumberSet = nextDescNumSet;
	if(N<10)
	cout<<N<<'\n';
	else
	FindDescendNumber(2);
	return 0;
	}

view raw 감소하는 수.cpp hosted with ❤ by GitHub