백준 BOJ 1038 - 감소하는 수

www.acmicpc.net/problem/1038

1038번: 감소하는 수

브루트포싱.

 

처음 보고 든 생각은 그냥 최대값까지 for문 돌리면서

감소하는 수들을 벡터에 담는 것이었는데,

이렇게 하자니 TLE가 나올것이 눈에 보여서

다른 방법으로 접근해보도록 했다.

 

가장 큰 감소하는 수는 9876543210일것이고,

가장 작은 감소하는 수는 0이 된다.

 

감소하는 수들의 특징은 수들의 정렬 순서가 내림차순으로 일정하다는 것인데,

확률과통계를 배우는 고딩들은 알겠지만

정렬 순서가 미리 정해진 수열을 만드는 경우의 수는 단순히 숫자를 뽑기만 해주면 된다.

따라서 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 수를 뽑아내는 경우의 수는

 

10C0 + 10C1 + 10C2 + .... 10C10 = 1024 - 1 ( 공집합 제외 ) 이므로

총 1023개가 나오게 된다.

 

이 1023개의 수를 재귀함수라던지를 적당히 사용해서 전부 벡터에 넣어준 다음,

정렬해서 출력만 해준다면 쉽게 AC가 나오는 문제.

 

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

void make(ll now, int k){
	v.push_back(now);
	for(int i=k-1; i>=0; i--){ make(now*10+i, i); }
	return;
}

int main(){
	for(int i=0; i<10; i++) make(i,i);
	sort(v.begin(), v.end());
	
	int n;
	scanf("%d", &n);
	printf("%lld", v.size()>n ? v[n] : -1);
	return 0;
}

구현자체는 쉬워서 풀만했다.