[백준/C++]#1174, 1038- 줄어드는 수, 감소하는 수

코드

#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector<ll> v;

void fun(int val, ll adder) {
    v.push_back(adder);
    for (int i=val-1; i>=0; i--) {
        fun(i, adder*10+i);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i=0; i<10; i++) fun(i,i);
    sort(v.begin(), v.end());
    v.insert(v.end(), 1000000, -1);
    int N;
    cin >> N;
    cout << v[N-1] << '\n';
    return 0;
}

풀이

줄어드는 수를 생성하는 함수를 만든다.

첫자리를 기준으로 하는 감소하는 수 집합들은 각자 베타적이다.

ex) 3으로 시작 <-> 2로 시작

       31                       21

 

1. 0부터 9까지를 첫자리로 하는 감소하는 수 집합을 vector에 저장한다.
2. vector를 전체 정렬한다.
3. 입력으로 들어오는 N이 감소하는 전체 수보다 클 경우들 대비해, 남은 공간에 -1을 저장한다. 

함수예시)

fun(3,3) → 앞자리 3인 모든 가능한 줄어드는 수

ex) 3210, 32, 31, 30, 321, 320, 310

---

 

+a

• 종료시점은 9876543210으로, int의 단위를 넘어서니 long long 사용
• 1000개정도니 부담없이 sort

 

• BOJ1038 (감소하는 수)의 경우 출력부분을 v[N]으로 변경하면 맞음!