[C++][BOJ 1174 줄어드는 수]

BOJ 줄어드는 수

 

문제 풀이

1. 가장 큰 줄어드는 수는 9876543210 이다. 10자리.

2. 기장 큰 수를 알고 있으므로 먼저 9876543210까지의 줄어드는 수를 모두 구한다.

3. 그 다음 정렬 후 n 번째 수를 출력, 범위 넘어가면 -1 출력

 

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void MakeIncreNum(ll num, int level, vector<ll>& v){
	if(level > 10) return;
	v.push_back(num);
	for(int i = num%10-1 ; i>=0 ;i--){
		MakeIncreNum(num*10 + i, level+1, v);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<ll> v;
	for(int i = 0; i <= 9 ; i++){
		MakeIncreNum(i,1,v);
	}
	
	sort(v.begin(),v.end());
	
	(n > v.size()) ? cout<< "-1" : cout<< v[n-1]  ;
	
}

- 문제를 보고 처음엔 n 과 비슷한 만큼 수를 찾고 그 다음 스텝을 가자라고 생각했는데

이러면 너무 복잡해졌다.

 

- 풀이 찾아보다 비트마스크로 해결하는 방법도 있었다.

지금 풀이와 비슷하다. 근데 잘 몰라 그냥 지금 푼 방법으로 해결했다.

 

 

참고

https://his130.tistory.com/206

https://lyzqm.blogspot.com/2017/12/1038-1174.html

https://henry121407.tistory.com/229