문제
https://www.acmicpc.net/problem/1038
풀이
한 자리 수는 그 자체로 감소하는 수이다.
0 1 2 3 4 5 6 7 8 9
두 자리 이상부터는 어떻게 구해야 할까? 일단 하나씩 다 적어보면서 규칙성을 파악해보자.
10
20 21
30 31 32
...
90 91 92 ... 98
...
210
310 / 320 321
410 / 420 421 / 430 431 432
...
910 / 920 921 / ... 987
...
9876543210 (최대) -> int 범위를 넘는다.
"현재 숫자의 첫번째 자리수 보다 작은 수들을 그 뒤에 하나씩 붙이면" 그 다음으로 감소하는 수를 구할 수 있다.
우리는 [0 1 2 3 4 5 6 7 8 9] 가 그 자체로 감소하는 수라는 걸 알고 있다. 그러면 그 다음으로 감소하는 수는?
'0'보다 작은 숫자는 없으므로 넘어간다. '1'보다 작은 숫자인 0을 뒤에 붙이면 '10'이 되며, 이것이 '9' 다음으로 감소하는 수가 된다.
그 다음으로 '2'보다 작은 숫자들을 하나씩 붙이면 '20', '21'이 나온다.
이렇게 N번째 숫자가 될 때까지 반복하면 된다.
그리고 감소하는 수를 순차적으로 구하기 위해 우리는 "더 작은 숫자를 더 우선적으로 빼는 과정"을 반복해야 한다. 0~9까지의 수 중에서 0부터 먼저 뽑아서 그 뒤에 더 작은 숫자들을 붙여야 한다.
이를 위해 선입선출 자료구조인 queue를 이용할 수 있다.
- 현재 숫자의 첫번째 자리 수를 구한다. (현재 숫자 % 10) = x
- 0 ~ (x - 1)까지의 숫자를 그 뒤에 하나씩 붙인다.
- 2번 과정에서 생성된 감소하는 수를 큐에 넣는다.
위와 같은 과정을 N번째 숫자를 구할 때까지 반복하면 된다. (구할 수 없으면 -1)
큐를 이용한 풀이
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n;
vector<ll> arr;
void solution() {
if(n >= 0 && n <= 9){
cout << n << endl;
return;
}
queue<ll> q;
for(int i = 0; i <= 9; i++){
q.push(i);
arr.push_back(i);
}
while(!q.empty()){
ll num = q.front();
q.pop();
int last = num % 10;
for(int i = 0; i < last; i++){
ll nextNum = num * 10 + i;
q.push(nextNum);
arr.push_back(nextNum);
}
}
if(n >= arr.size()){
cout << -1;
}else{
cout << arr[n];
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
solution();
return 0;
}백트래킹
백트래킹으로도 풀 수 있다. 사실 이 방법이 떠올리기 더 쉬운 거 같다. 위의 풀이와 마찬가지로 N번째로 감소하는 수를 구하기 위해 배열을 이용할 것이다.
감소하는 수를 저장하는 배열을 만들어두면, N번째 값에 O(1)의 시간복잡도로 빠르게 접근할 수 있기 때문이다.
그렇다면, 감소하는 수를 어떻게 구할까??
아래와 같이 dfs 함수를 구현하면 된다.
void dfs(ll num, int digit){
if(digit > 10) return; // 최대 9876543210
arr.push_back(num);
for(int i = 0; i < 10; i++){
if(num % 10 > i){
dfs(num * 10 + i, digit + 1);
}
}
}dfs(0, 1)
-> 0
dfs(1, 1)
-> 1 10
dfs(2, 1)
-> 2 20 21 210
dfs(3, 1)
-> 3 30 31 310 32 320 321 3210
dfs(4, 1)
-> 4 40 41 410 42 420 421 4210 43 430 431 4310 432 4320 4321 43210
...
dfs(9, 1)
-> ... 987654321 9876543210
총 개수는 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^9 = 2^10 - 1 = 1023개가 된다.
이렇게 모든 경우의 수를 구하고 오름차순으로 정렬한 다음 n번째 감소하는 수인 arr[n]을 출력하면 된다. (n이 arr 크기와 같거나 더 크면 -1 출력)
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n;
vector<ll> arr;
void dfs(ll num, int digit){
if(digit > 10) return; // 최대 9876543210
arr.push_back(num);
for(int i = 0; i < 10; i++){
if(num % 10 > i){
dfs(num * 10 + i, digit + 1);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < 10; i++){
dfs(i, 1);
}
sort(arr.begin(), arr.end());
// 0번째 -> arr[0]
// 1번째 -> arr[1]
// ...
// (n-1)번째 -> arr[n-1] (size: n)
// n번째 -> arr[n] (size: n + 1)
// 따라서, n < arr.size() 인 경우에만 n번째 수 구할 수 있음.
if(n >= arr.size()){
cout << "-1";
}else{
cout << arr[n];
}
return 0;
}