백준 BOJ 1174 - 줄어드는 수

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

1174번: 줄어드는 수

브루트포스 문제.

줄어 드는 수 중 가장 큰 수는 9876543210 이므로,

0부터 숫자를 1씩 증가하면서 "줄어드는 수" 인지 체크하는 방법은 TLE를 받게 된다.

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 순으로 배열된 배열에서 각각의 숫자를 포함하거나

포함하지 않는 경우를 기준으로 브루트포싱을 해주면

 

순회 횟수가 2^10 밖에 되지 않으므로 무난하게 해결할 수 있다.

비트마스킹을 통해서 브루트포싱을 진행했다.

 

가장 큰 수인 9,876,543,210 은 90억으로 INT범위를 넘어가니

long long 형을 사용해줘야 한다.

 

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

bool chk(int k){
	int now = k%10;
	while(k/10){
		k/=10;
		if(k%10 <= now) return false;
		else{
			now = k%10;
		}
	}
	return true;
}

vector<ll> v;

int arr[] = {9,8,7,6,5,4,3,2,1,0};

int main(){
	for(int i=1; i<(1<<10); i++){
		int tmp = i;
		ll val = 0;
		int idx = 0;
		
		while(tmp){
			if(tmp%2 == 1) val = val*10 + arr[idx];
			tmp /= 2;
			idx++;
		}
		v.push_back(val);
	}
	
	sort(v.begin(), v.end());
	
	int N;
	cin >> N;
	if(v.size() < N) cout << -1;
	else cout << v[N-1];
	return 0;
}