1174 줄어드는 수(C++)

줄어드는 수

N번째 있는 ‘줄어드는 수’를 구하는 문제

1. 문제

---

간단 설명

N번째 있는 줄어드는 수를 구하는 문제

‘줄어드는 수’란 321, 987처럼 큰 자리수에서 작은자리수로 갈 때,

각 자리의 숫자도 줄어드는 수를 말한다

첫번째 줄어드는 수(N=1)는 0, 두번쨰 줄어드는 수(N=2)는 1, …

이런식으로 갈때, N이 주어질 때, 그에 해당하는 수를 출력하는 문제

2. 문제 분석

---

주의점

• N이 1,000,000 이하의 자연수이다.

  이는 백만번째 줄어는 수가 뭔지 물어보는거지, 해당 수가 백만보다 작다는 뜻이 아니다.

  즉, 해당 수는 int형보다 클 수도 있다

• 가장 큰 줄어드는 수는 10진수의 한계로 인해 1022번째 등장하는 9876543210 이다.

• 이를 이용해 1022번째 이후로는 구할 필요가 없다. 해가 없기 때문

• bruteforce로 시도할 시, 시간 복잡도 확인 필요

  가장 간단하게 생각할 수 있는 완전 탐색 방법은

  n이 1022일때, 줄어드는 수가 9876543210이라면

  i=0부터 9876543210 까지 반복문 돌려서 i가 줄어드는 수인지 확인하는 방법.

  이미 약 100억번 가까이 루프를 돌기 떄문에 시간초과임

알고리즘

• 대신 DFS를 이용해서 해결한다

dfs(level, sum)을 이용해,

각 숫자를 sum에 추가할지 말지 결정한다.

그림 안의 0는 sum을 의미한다. 9를 추가하면 0+9가 되고,

9에 8을 추가한다면 98이 되는 식으로 진행한다

level = 0 : 9를 선택하고 숫자에 추가하기 혹은 패스

level = 1 : 8을 선택하고 숫자에 추가하기 혹은 패스
... 
level = 9 : 0를 선택하고 숫자에 추가하기 혹은 패스

1. n을 입력받는다
2. dfs 함수를 통해 생성할 수 있는 모든 줄어드는 수를 구한다
	2-1. 줄어드는 수를 구하고 정렬한뒤, 중복 원소를 제거한다
3. 결과 벡터에 저장된 n번째 원소를 출력한다
	3-1. n의 최대값은 1022이므로, 1023 이상은 -1을 출력한다

필요변수

int n (n<= 1,000,000)

결과를 저장할 벡터 result. 결과는 int형을 초과할 수 있기 때문에 long long int 사용

dfs(level, num) 함수. num 또한 long long int 사용

sort, unique를 이용하기 위한 algorithm 헤더

3. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
vector<long long int> result;

void dfs(int level, long long int num) {
	result.push_back(num);
	if (level >= 10) return;

	dfs(level + 1, num * 10 + arr[level]);
	dfs(level + 1, num);
}

int main() {
	int n;
	cin >> n;

	if (n > 1023) {
		cout << -1;
		return 0;
	}

	dfs(0, 0);

	sort(result.begin(), result.end());
	result.erase(unique(result.begin(), result.end()), result.end());

	cout << result[n-1];

	return 0;
}