티스토리 뷰

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

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net

#include <iostream>
#include <string>
using namespace std;

int N;
int answer = 9;
long long ans = -1;


void backtracking(int n, int cnt, int jarisu, string s) {
	if (cnt == jarisu) {
		answer++;
		if (answer == N) {
			ans = stoll(s);
		}
		return;
	}
	if (n  < jarisu - cnt) {
		return;
	}
	for (int i=0; i<n; i++){
		s += (char)('0' + i);
		backtracking(i, cnt + 1, jarisu, s);
		s.pop_back();
	}
}


int main() {
	cin >> N;
	if (N >= 0 && N <= 9) {
		ans = N;
	}
	else{
		int jarisu = 2;
		while (jarisu <= 10) {
			for (int i = 1; i <= 9; i++) {
				backtracking(i, 1, jarisu, to_string(i));
			}
			if (ans != -1)
				break;
			jarisu++;
		}
	}
	cout << ans << "\n";
	return 0;
}

백트래킹을 이용하여 풀이했다.

 

자리수를 고른 뒤(자리수는 10자리까지만 따져줌=>가장 큰 감소하는 수가 9876543210 이기 때문), 숫자의 가장 첫번째 수를 골라준 뒤, backtracking 함수를 호출한다.

 

backtracking 함수에서 현재 고른 수는 n으로, 다음 수를 탐색할 때 (0~n-1) 범위에서 탐색하여 백트래킹 해준다.

이때, 유망성을 따져주어 만약 채워야 하는 자리 숫자만큼 가능한 숫자가 없을 때 그 경우는 탐색하지 않는 것으로 한다. 

 

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함