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

문제링크: https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

많이 고민한 문제입니다.

첫번째로 dp적인 사고로 생각되지 않아 고민하였습니다.

 

저는 가변 배열인 vector를 사용하여 해결하였습니다. 

1. 1~9 을 미리 vector에 넣고 
2. 순서대로 자신보다 작은 수를 뒤에 붙여 vector에 다시 넣습니다.
3. 즉 1인 경우 10을 vector에 2인 경우 20 21 을 vecor에 넣습니다.

이 과정을 반복하며 vector 를 구성하여 문제를 해결했습니다.

 

 

 

 

 

하지만 이문제에는 함정이 존재합니다.

만약 N번째 감소하는 수가 없다면 -1을 출력한다.

위 조건이 함정입니다. 

 

생각해보니 9876543210 << 이상부터는 더이상의 감소하는 수가 존재하지 않습니다.

 

그렇다면 9876543210 은 몇번째 숫자일까요?

 

1의 자리수 일때는 1~9  -> 10C1

2의 자리수 일때는 1 + 2 + ~ + 9 =45  -> 10C2

 

.

.

.

.

9의 자리수 일때는 1 -> 10C10

즉 아래 식만큼 가능합니다.

 

1023입니다.

하지만 하나도 선택하지 않을때를 빼면 1022번까지만 가능합니다. 이후 숫자는 -1 을 출력하게끔 구현해야함

 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector <long long> que;
int n = 0, cnt = 0;


int main() {


	cin >> n;
	if (n > 1022) {
		cout << -1 << endl;
		return 0;
	}
	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i <= 9; i++) { //초기값 지정
		que.push_back(i);
		cnt++;
	}
	

	for(int i=0;i<que.size();i++) {
		if (cnt >= n)
			break;
		long long n = que[i];
		
		for (int i = 0; i <= 9; i++) {
			if (n % 10 > i)
				que.push_back(n * 10 + i),cnt++;
			
		}

	}
	cout << que[n-1] << endl;
	return 0;

}