백준 14791번 Tidy Numbers - C++(cpp) 풀이

---

 

1. 10^18 이하의 tidy number를 모두 구한다.
2. tidy number들을 정렬한 뒤, N의 upper bound를 구한다.
3. tidy_numbers[upper_bound-1]이 N 이하인 가장 큰 tidy number이다.

 

1. 10^18 이하의 tidy number를 모두 구한다.

 10^18 이하의 tidy numbers는 총 4,686,824개이다. 생각보다 많지 않으므로 이것을 모두 구해주자. tidy number를 문자열로 생각하면, 모든 부분 문자열 또한 tidy number이다. 따라서 길이가 len인 tidy number X에, X의 마지막 문자보다 크거나 같은 문자를 덧붙이면 길이가 len+1인 tidy number를 만들 수 있다. 이러한 사실을 사용해서 재귀를 통해 모든 tidy number를 구해준다.

 

2. tidy number들을 정렬한 뒤, N의 upper bound를 구한다.

모든 tidy number를 구했으면, 오름차순으로 정렬한 뒤 N의 upper bound를 구해준다.

 

3. tidy_numbers[upper_bound-1]이 N 이하인 가장 큰 tidy number이다.

 upper bound 직전의 수가 N이하인 tidy number 중에 가장 큰 수가 된다.

반응형

---

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll N;
vector<ll> tidy;

void calc_tidy(ll x) {
    tidy.push_back(x);
    
    if (x > 100000000000000000) return;
    
    for (int i=x%10; i<=9; i++) {
        calc_tidy(x*10+i);
    }
}

int upper_bound(ll x) {
    int lo = 0, hi = tidy.size();
    
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (tidy[mid] <= x) lo = mid + 1;
        else hi = mid;
    }
    
    return lo;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for (int i=1; i<=9; i++) calc_tidy(i);
    sort(tidy.begin(), tidy.end());
    
    int T;
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        cin >> N;
        
        int ub = upper_bound(N);
        ll ans = tidy[ub-1];
        
        cout << "Case #" << t << ": " << ans << "\n";
    }

    return 0;
}