문제 설명
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.
https://www.acmicpc.net/problem/1038
제한 사항
풀이
문제를 요약하면, N번째 감소하는 수를 구하는 것이다.
감소하는 수란 10, 21, 20처럼 첫자리부터 끝 자리까지 수가 감소하는 수를 말한다.
11이나 22는 감소하는 수가 아니다.
문제를 풀기 위해서는 규칙을 찾아내야 한다.
규칙을 찾기 위해 감소하는 수를 차례대로 적어보자.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, ..., 9876543210우선, 한 자리 수는 모두 감소하는 수이다.
그리고 가장 큰 감소하는 수는 9876543210이다.
9보다 큰 한 자리 수는 없기 때문에 9 앞에 어떠한 수를 붙여도 감소하는 수가 되지 않는다.
그럼, 두 자리 수를 살펴보자.
여기서 규칙을 찾을 수 있다.
두 자리 감소하는 수는 10, 20, 21, 30...이다.
가장 큰 수부터 차례대로 자릿수를 구성하는 것을 볼 수 있다.
즉, 1에 1보다 작은 수인 0을 붙여 10, 2보다 작은 수인 0, 1을 붙여 20, 21 이렇게 진행된다.
그렇다면 이러한 규칙을 이용하여 N번째 감소하는 수를 어떻게 찾을까?
방법은 반대로 생각하는 것이다.
가장 앞자리 수보다 작은 수를 뒤로 이어 붙이는 것이 아니라 모든 한 자릿수에 대해 자신보다 큰 수를 앞에 붙인다고 생각하면 된다.
예를 들어, 0에서 시작했다면, {10, 20, 30, 40, 50, 60, 70, 80, 90}을 만들 수 있다.
또 만들어진 수에서 똑같은 과정을 진행하면 된다.
이렇게 만들어진 수를 정렬하여 N번째 감소하는 수를 찾으면 된다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> nums;
void dfs(long long num, int first, int digit)
{
nums.push_back(num);
for (int i = first + 1; i < 10; i++)
{
long long add = i * pow(10, digit);
dfs(num + add, i, digit + 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cin >> N;
for (int i = 0; i < 10; i++)
{
dfs(i, i, 1);
}
sort(nums.begin(), nums.end());
if (nums.size() <= N) cout << -1;
else cout << nums[N];
return 0;
}
