BOJ 1038 - 감소하는 수

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

1038번: 감소하는 수

 

어떤 숫자가 맨 앞자리 부터 맨 끝자리 까지 수가 감소하는 모양이면, 감소하는 수 라 부른다

예를들면, 321, 54321, 620 등 은 감소하는 수 이고, 881, 922 등은 감소하는 수가 아니다.

 

처음에 이 문제를 풀때는, 수의 범위를 잘못 잡아서 틀렸었다

입력 N 은 N 번째 감소하는 수가 무엇인지 묻는 것인데,

#define MAX 1000000 으로 잡고 0 ~ MAX 까지 돌려서 감소하는 수인지 검증을 하고 N 번째에 해당할때 

출력을 하려고 했다.

그래서 아래와 같이 코드를 짰었으나,

 

- c++

#include <iostream>
#include <vector>
#define MAX 1000000
 
using namespace std;
 
int N;
vector<int> vec;
 
bool promising(int num) {
    bool check = false;
    int temp = -1;       // 뒷자리수
    int remainder = -1;  // 앞자리수
    while (num) {
        remainder = num % 10;
        if (temp == -1) {
            temp = remainder;
        } else if (temp != -1 && temp < remainder) {
            check = true;
            temp = remainder;
        } else if (temp != -1 && temp >= remainder) {
            return false;
        }
        num /= 10;
    }
 
    if (check) {
        return true;
    } else {
        return false;
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    int cnt = 0;
 
    for (int i = 0; i < MAX; i++) {
        if (i / 10 == 0) {
            vec.push_back(i);
        } else {
            if (promising(i)) {
                vec.push_back(i);
            }
        }
    }
 
    int size = vec.size();
    if (N >= size) {
        cout << -1;
    } else {
        cout << vec[N];
    }
 
    return 0;
}

 

 

이렇게 짜게 되면, 입력의 수가 최대 987654 까지만 나오게 되어서 모든 자연수에 한해서 처리할 수 없었다

 

자연수에서 감소하는 수의 최대 값은 9876543210 이며, 이 값은 N = 1022 번째일때 해당한다고 한다.

위의 코드는 최대 N 이 846 밖에 되지 않았다.

 

그래서 MAX 를 10000000000 까지 늘릴까 생각했으나, 이는 당연히 시간초과이기 때문에, 통과할수 없었다.

 

오랜 시간을 고민하다가 답이 안보이길래, 다른 사람들의 풀이를 찾아봤더니,

 

두가지의 풀이 방식이 인상적이었다.

 

하나는 재귀함수를 통해서 맨 앞자리 수를 따서 배열을 만들어가는 것이고,

다른 하나는 재귀방식이 아닌 반복문의 형식으로 큐를 이용해서 만들어간것이다.

 

https://rile1036.tistory.com/102

[백준] 1038번 감소하는 수 c++ DP

https://kswims.tistory.com/139

[백준] 1038번 감소하는 수, 1174번 줄어드는 수

 

- c++

-재귀함수 방식

#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
 
using namespace std;
 
vector<ll> vec;
int N;
 
void solution(ll index, int cnt) {
    if (cnt > 10) return;
 
    vec.push_back(index);
 
    for (int i = 0; i < 10; i++) {
        if (index % 10 > i) {
            solution(index * 10 + i, cnt + 1);
        }
    }
    return;
} 
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    for (int i = 0; i < 10; i++) {
        solution(i, 1);
    }
 
    sort(vec.begin(), vec.end());
 
    ll answer = (vec.size() <= N) ? -1 : vec[N];
 
    cout << answer;
 
    return 0;
}

 

 

- c++

-큐를 이용한 반복문 방식

#include <iostream>
#include <queue>
 
using namespace std;
 
int N;
queue<int> decrease;
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
 
    int cnt = 0;
    int i, j, tmp;
 
    if (N <= 10) {
        cout << N << '\n';
    } else if (N == 1022) {
        cout << 9876543210 << '\n';
    } else if (N >= 1023) {
        cout << "-1" << '\n';
    } else {
        for (i = 1; i < 10; i++) {
            decrease.push(i);
            cnt++;
        }
 
        while (cnt < N) {
            i = decrease.front();
            decrease.pop();
            tmp = i % 10;
 
            for (j = 0; j < tmp; j++) {
                decrease.push(i * 10 + j);
                cnt++;
                if (cnt == N) {
                    cout << i * 10 + j << '\n';
                    break;
                }
            }
        }
    }
 
    return 0;
}

 

 

 

 

참 머리 좋은 사람들이 많다 

어떻게 이런 코드를 생각해내는지

놀랍다