[백준] 1038번 감소하는 수

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

1038번: 감소하는 수

처음에는

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

int n;
set<long long> s;
long long number;


void permutation(int num, vector<int> result) {
	if (s.size() > n)
		return;
	if (num == result.size()) {
		number = 0;
		for (int i = result.size() - 1; i >= 0; i--) {
			number += (pow(10, result.size() - 1 - i) * result[i]);
		}
		s.insert(number);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		result[num] = i;
		if (num > 0) {
			if (result[num] < result[num - 1])
				permutation(num + 1, result);
		}
		else
			permutation(num + 1, result);
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	int i = 1;
	while (true) {
		permutation(0, vector<int>(i));
		if (s.size() > n)
			break;
		i++;
	}

	int cnt = 0;
	for (set<long long>::iterator iter = s.begin(); iter != s.end(); iter++) {
		if (cnt == n) {
			cout << *iter;
			break;
		}
		cnt++;
	}
	return 0;
}

이렇게 제출했다.

나는 나름대로 재귀를 호출하기 전에 result[num] < result[num - 1]인지 확인하고 조건에 맞을 경우에만 호출했기 때문에 가지치기를 했다고 생각했다. 하지만 시간초과가 나왔다.

 

그래서

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

int n;
set<long long> s;
long long number;


void permutation(int num, vector<int> result) {
	if (s.size() > n)
		return;
	if (num == result.size()) {
		number = 0;
		for (int i = result.size() - 1; i >= 0; i--) {
			number += (pow(10, result.size() - 1 - i) * result[i]);
		}
		s.insert(number);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		result[num] = i;
		if (num > 0) {
			if (result[num] < result[num - 1] && result[num] >= result.size() - 1 - num)
				permutation(num + 1, result);
		}
		else {
			if(result[num] >= result.size() - 1)
				permutation(num + 1, result);
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	int i = 1;
	while (true) {
		permutation(0, vector<int>(i));
		if (s.size() > n)
			break;
		i++;
	}

	int cnt = 0;
	for (set<long long>::iterator iter = s.begin(); iter != s.end(); iter++) {
		if (cnt == n) {
			cout << *iter;
			break;
		}
		cnt++;
	}
	return 0;
}

이렇게 제출했는데 또 시간초과가 났다. 9876543210보다 큰 감소하는 수는 없는데도 계속 구했기 때문이다.

 

그래서 다시

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

int n;
set<long long> s;
long long number;


void permutation(int num, vector<int> result) {
	if (num == result.size()) {
		number = 0;
		for (int i = result.size() - 1; i >= 0; i--) {
			number += (pow(10, result.size() - 1 - i) * result[i]);
		}
		s.insert(number);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (result.size() - num - 1 <= i && (num == 0 || (num > 0 && result[num - 1] > i))) {
			result[num] = i;
			permutation(num + 1, result);
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n;
	int i = 1;
	for (int i = 1; i <= 10; i++) {
		permutation(0, vector<int>(i));
	}
	int cnt = 0;
	bool flag = false;
	for (set<long long>::iterator iter = s.begin(); iter != s.end(); iter++) {
		if (cnt == n) {
			cout << *iter;
			flag = true;
			break;
		}
		cnt++;
	}
	if (!flag)
		cout << -1;
	return 0;
}

이렇게 제출했는데 0ms로 성공했다. 9자리 감소하는 수를 구하는데 맨 앞의 숫자가 8 미만이면 이미 틀려먹은 것이다.

10자리 감소하는 수를 구하는데 맨 앞의 숫자가 9 미만이면 이미 틀려먹은 것이다. 이런 식으로 가지치기를 해주었다.