백준 1038 c++ "감소하는 수" -PlusUltraCode-

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

 

[필자 사고]

문제를 보고 시간복잡도를 생각했다.

dfs를 이용하면 모든 수를 시간안에 완료할 수 있을 지 ..

일의 자리 수부터 시작하여 마지막 digit을 관리하면서 dfs로 다음 수로 나아가게 되면 N의 최대가 1000000이기 때문에

1억을 넘지 않으므로 충분히 시간복잡도가 널널하다. 

좋다 이방법으로 가보자 하는 식으로 문제를 해결했다. 

[코드 해설]

Input() 함수

• 사용자로부터 정수 N을 입력받는다.
• N은 "N번째 감소하는 수"를 구하기 위한 목표 인덱스이다.

---

dfs(long long number, int last_digit) 함수

• 감소하는 수를 재귀적으로 생성하는 백트래킹 함수이다.
• number는 현재까지 만든 감소하는 수이며,
• last_digit은 현재 수의 마지막 자릿수이다.
• 현재 수 number를 결과 배열 arr에 저장한다.
• 다음 자릿수는 반드시 현재 자릿수보다 작은 수여야 하므로,
  0부터 last_digit - 1까지의 수를 오른쪽에 붙여가며 다시 dfs를 호출한다.

---

Game_Start() 함수

• 감소하는 수 생성을 시작하는 메인 함수이다.
• 한 자리 수 0부터 9까지를 시작점으로 하여 각각에 대해 dfs를 호출한다.
• 이 과정에서 가능한 모든 감소하는 수가 arr에 저장된다.
• 생성된 수들을 오름차순으로 정렬한다.
• 배열의 크기보다 N이 크거나 같다면 존재하지 않는 수이므로 -1을 출력한다.
• 그렇지 않으면 arr[N] 값을 출력한다.

---

main() 함수

• 프로그램의 시작점이다.
• Input()을 호출해 입력을 받고,
• Game_Start()를 호출해 계산 및 출력 작업을 수행한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<long long> arr;

void Input() {
	cin >> N;

}

void dfs(long long number, int last_digit) {

	arr.push_back(number);
	for (int i = 0; i < last_digit; i++) {
		dfs(number * 10 + i, i);
	}
}

void Game_Start() {
	
	for (int i = 0; i < 10; i++) {
		dfs(i, i);
	}

	sort(arr.begin(), arr.end());

	if (N >= arr.size()) {
		cout << "-1";
	}
	else {
		cout << arr[N];
	}
}

int main(void) {
	Input();
	Game_Start();

}