안녕하세요! 오늘은 BOJ 1038 - 감소하는 수 문제를 풀어볼게요.
접근
문제를 읽어보면, 음이 아닌 정수 (0과 자연수) X의 자릿수가 가장 큰 자릿수부터 가장 작은 자릿수까지 감소만 하는 수가 '감소하는 수'라고 정의했네요.321과 950은 백의 자리부터 일의 자리까지 전부 감소만 하니 감소하는 수지만, 322는 같은 숫자가 있고, 958은 감소하다가 증가했으니 감소하는 수가 아니라고 해요.
0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수라고 하네요.
쭉쭉 이어서 써보면, 10이 10번째 감소하는 수가 될 거예요.
그리고 11~19는 일의 자리 수가 십의 자리 수보다 크거나 같으니, 20이 11번째 감소하는 수가 되겠네요.
21은 12번째 감소하는 수지만, 11~19와 마찬가지로 22~29도 감소하는 수가 안 돼요.
30, 31, 32, 40, 41, 42, 43, 50, 51... 이렇게 감소하는 수를 쭉 쓸 수 있겠네요.
결국 가장 큰 감소하는 수는 0~9의 숫자를 모두 내림차순으로 쓴 9876543210이 될 거예요.
맨 앞자리 숫자가 클수록 뒤에 더 많은 숫자가 올 수 있으니, 맨 앞자리 숫자를 기준으로 케이스 분류를 해볼게요.
맨 앞자리 숫자가 0일 경우엔 0번째 감소하는 수인 0만 가능해요. (0 : 1가지)
맨 앞자리 숫자가 1일 경우엔 1 자체도 감소하는 수인데, 뒷자리에 0도 올 수 있으니, 10도 감소하는 수예요. (1, 10 : 2가지)
맨 앞자리 숫자가 2일 경우엔 2도 감소하는 수이고, 뒷자리에 0 또는 1이 올 수 있으니, 20, 21, 210도 감소하는 수예요. (2, 20, 21, 210 : 4가지)
맨 앞자리 숫자가 3일 경우엔 3도 감소하는 수이고, 뒷자리에 0 ~ 2가 올 수 있으니, 30, 31, 310, 32, 320, 321, 3210도 감소하는 수예요. (3, 30, 31, 310, 32, 320, 321, 3210 : 8가지)
맨 앞자리 숫자가 4일 경우엔 4도 감소하는 수이고, 뒷자리에 0 ~ 3이 올 수 있으니, 40, 41, 410, 42, 420, 421, 4210, 43, 430, 431, 4310, 432, 4320, 4321, 43210도 감소하는 수예요. (4, 40, 41, 410, 42, 420, 421, 4210, 43, 430, 431, 4310, 432, 4320, 4321, 43210 : 16가지)
뭔가 숫자들의 반복되는 형태가 보이지 않으시나요? 그리고 가능한 경우의 수가, 1, 2, 4. 8, 16이면 무언가 규칙성이 있어 보이지 않나요?
규칙성을 바탕으로 맨 앞자리 숫자가 5~9일 때 경우의 수는 어느 정도 구조가 반복될 것임이 예측되니, 2^5, 2^6, ... , 2^9가지 경우의 수일 것 같네요.
전체 경우의 수의 합을 구해보면, (2^10)-1 = 1023가지 경우의 수로 케이스가 몇 개 안 되는 것을 알 수 있게 됐어요.
이 정도면 백트래킹으로 미리 모든 감소하는 수를 구해두고 정렬해서 N번째 감소하는 수를 출력하도록 구현해도 문제가 없을 것 같으니, 구현을 해보도록 할게요.
구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> result;
void func(long long temp, int k) { // 마지막으로 고른 수가 k이고 현재 수가 temp일 때!
if (k == 1) { // 마지막으로 고른 수가 1이면 마지막 남은 자릿수를 채우는 방법은 0뿐이므로..
result.push_back(temp);
return;
}
for (int i = 0; i < k; i++) { // 다음 자리수는 0 ~ k-1 중에서 고르기 (같은 수가 나오면 감소하는 수 아님!)
result.push_back(temp + i); // 결과 벡터에 값 넣어주기
if (i != 0) func((temp + i) * 10, i);
// 0이 아닌 수로 끝났을 때 그 다음 자릿수를 고르려면, 현재 수에 10배 해준 값과 마지막 자릿수를 담아 재귀..
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
func(0, 10); // 백트래킹
sort(result.begin(), result.end()); // 오름차순 정렬
int n;
cin >> n;
if (n >= result.size()) { // 존재하지 않는 감소하는 수를 물었을 때
cout << -1;
return 0;
}
cout << result[n];
return 0;
}
전체적인 구조는 백트래킹으로 result 벡터에 모든 감소하는 수를 구해주고, result 벡터를 오름차순으로 정렬해서, N을 입력받고 N번째 감소하는 수를 구해주었어요.
이때 N이 벡터의 크기보다 크거나 같을 경우에는(0이 0번째 감소하는 수이므로, 1022번째 감소하는 수가 최대인 9876543210이고, 1023번째부터 존재하지 않음) 감소하는 수가 존재하지 않으므로 -1을 출력해 줘요.
vector<long long> result;
void func(long long temp, int k) { // 마지막으로 고른 수가 k이고 현재 수가 temp일 때!
if (k == 1) { // 마지막으로 고른 수가 1이면 마지막 남은 자릿수를 채우는 방법은 0뿐이므로..
result.push_back(temp);
return;
}
for (int i = 0; i < k; i++) { // 다음 자리수는 0 ~ k-1 중에서 고르기 (같은 수가 나오면 감소하는 수 아님!)
result.push_back(temp + i); // 결과 벡터에 값 넣어주기
if (i != 0) func((temp + i) * 10, i);
// 0이 아닌 수로 끝났을 때 그 다음 자릿수를 고르려면, 현재 수에 10배 해준 값과 마지막 자릿수를 담아 재귀..
}
}
백트래킹 부분만 따로 떼어내서 자세히 살펴볼게요.
처음 func를 호출할 때에는 func(0, 10)으로 호출해요.초기값 temp = 0이고, i = 0~9까지 result 벡터에 (temp + i) = 0 ~ 9가 감소하는 수이니 넣어줄 거예요.그리고 i = 0인 경우는 다음 자릿수를 사용하지 못하므로, i가 0이 아닌 경우에만 func((temp + i) * 10, i)를 호출해요.여기에서 (temp + i) * 10을 해주어야 다시 func에서 다음 자릿수를 더해줄 수 있겠죠?
그리고 i는 마지막으로 고른 자릿수를 뜻해요. 마지막 자릿수가 i이니, i보다 작은 수만 다음 자릿수에서 골라야 하기 때문에 인자로 넣어주었어요.
k = 1일 경우에는 결국 마지막으로 고른 자릿수가 1이면 다음 자릿수는 0 뿐이므로 temp를 그대로 벡터에 push 해주고, return 하도록 했어요.
백트래킹 부분이 글로 설명하기에 조금 벅찬 느낌이 있는데, 직접 수를 넣어보면서 이해하시는 편이 가장 쉬울 것 같아요.
