[C++] 감소하는 수 (1038번)

감소하는 수 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

24825

7741

6089

33.673%

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

---

문제풀이

다른 사람 풀이보고 풀었다.. 이걸 어떻게 생각해냈지.. 충격주의 스포주의 매우놀람주의

감소하는 수의 개수는 2^10-1 = 1023 개이다.

어떻게 이걸 아느냐?

집합 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 의 부분집합의 개수에 공집합을 뺀것이다.

이게 어떻게 감소하는 수냐?

저 집합에서 어떤 부분집합을 만들던 간에 감소하는 수가된다... 천재야...

{2, 5, 8} 이던,, {1, 9} 이던 어떤식으로 부분집합을 빼와도 감소하는 수를 만들수 있다.

오우쉣...

그럼 1023개 밖에 안되니까 그냥 브루트포스로 다 찾아서 정렬해준뒤 출력하면 된다. 정말이지 대단하다.

 

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

using namespace std;

int n;
vector<long long int> v;

void func(int now, string value) {
    if(value.size()>=1)
        v.push_back(stoll(value));
    for(int i=now; i<=9; i++) {
        func(i+1, to_string(i)+value);
    }
}

int main() {
    cin >> n;
    func(0, "");
    sort(v.begin(), v.end());
    if(n >= 1023)
        cout << -1;
    else
        cout << v[n];
    return 0;
}

 

참고

https://blog.encrypted.gg/142