백준 1174 - 줄어드는 수

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

 

문제의 조건은 숫자가 줄어들기만 하면 되기 때문에 탐색이 간단한 편임을 눈치챌 수 있다.

 

"9876543210"에서 순서대로 몇 개의 문자를 선택하면 그것이 줄어드는 수이므로 $ 2^{10}$번의 연산으로 모든 경우의 수를 확인할 수 있다.

 

적당한 방법을 통해 줄어드는 수를 모두 구한 후 답을 출력해 주자.

 

정답 코드 - C++

#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using pii = pair<int, int>;
using ll = int_fast64_t;
 
vector<ll> vec;
 
void solve()
{
  int n;
  cin >> n;
 
  for (int i = 1; i < (1 << 10); i++)
  {
    string wow;
 
    for (int j = 0; j < 10; j++)
    {
      if (i & (1 << j))
      {
        wow.push_back("9876543210"[j]);
      }
    }
 
    if (wow.empty()) wow = "0";
 
    vec.push_back(stoll(wow));
  }
 
  sort(begin(vec), end(vec));
  --n;
  if (vec.size() <= n) cout << -1;
  else cout << vec[n];
}
 
int main()
{
#ifdef LOCAL
//  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
 
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}