백준 1038번 감소하는 수 - C++(cpp) 풀이

---

 

1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다.
2. 따라서 감소하는 수의 총개수는 2^10-1 = 1023개
3. 감소하는 수를 모두 구한 뒤 정렬한다.

 

1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다.

 숫자 목록이 주어지면 해당 수들로 만들 수 있는 감소하는 수는 하나로 결정된다. 또한 항상 감소해야 하므로 같은 숫자가 두 번 이상 등장하는 일은 없다. 따라서 10개 숫자 0-9에 대해 각각을 사용할 것인지를 결정하기만 하면 감소하는 수가 결정되고, 그 감소하는 수는 선택한 숫자들을 큰 수부터 차례로 나열한 것이 된다.

 

2. 따라서 감소하는 수의 총 개수는 2^10-1 = 1023개

 10개 숫자에 대해 사용 여부를 결정해주면 되기 때문에 감소하는 수의 총개수는 2^10-1 = 1023이 된다.

 

3. 감소하는 수를 모두 구한 뒤 정렬한다.

 1023개밖에 되지 않으므로 모두 구한 뒤 정렬해도 충분하다. 비트마스킹을 사용해 브루트포스로 모든 수를 구한 뒤, 정렬해준다.

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int N;
vector<ll> arr;

ll make_decreasing_num(int mask) {
    ll ret = 0;
    
    // 큰 수부터 차례로 나열하면 감소하는 수가 완성된다.
    for (int i=9; i>=0; i--) {
        if ((mask & (1 << i)) != 0) {
            ret *= 10;
            ret += i;
        }
    }
    
    return ret;
}

void find_all_decreasing_nums() {
    // 0-9 중 사용할 수들을 선택하면 감소하는 수가 결정된다.
    for (int i=1; i<(1 << 10); i++) {
        arr.push_back(make_decreasing_num(i));
    }
}

ll nth_decreasing_num(int x) {
    find_all_decreasing_nums();
    sort(arr.begin(), arr.end());
    
    if (arr.size() <= x) return -1;
    else return arr[x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    cout << nth_decreasing_num(N);

    return 0;
}