[BOJ] 1038번 : 감소하는 수

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
vector<bool> v(10, 0);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int n; 
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= 10; i++) {
		v[10 - i] = 1;
		do {
			if (cnt != n) {
				cnt++; 
				continue;
			}
			for (int i = 0; i < 10; i++) {
				if (v[i]) cout << 9 - i;
			}
			return 0;
		} while (next_permutation(v.begin(), v.end()));
	}
	cout << -1;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1038.cpp

basic-algo-lecture/0x12/solutions/1038.cpp at master · encrypted-def/basic-algo-lecture

do while (next_pernutation)을 이용해, 사전식 조합을 완성한 후, 내가 원하는 순번이 오면, 값을 출력해서 보여주는 로직이다. 멋있는 풀이다.

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/33441c53abac4efd85f455173bfef20a
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
vector<ll> nums; 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  // brute를 2진수로 나타냈을 때의 값을 가지고 임의의 부분집합을 얻어내고, 대응되는 감소하는 수를 nums에 추가
  for(int i = 1; i < 1024; i++){
    int brute = i;
    ll num = 0;
    for(int j = 9; j >= 0; j--){
      if(brute % 2 == 1) num = 10*num + j;
      brute /= 2;
    }
    nums.push_back(num);
  }
  sort(nums.begin(), nums.end());
  int n;
  cin >> n;
  if(n > 1022) cout << -1;
  else cout << nums[n];
}

/*
집합 {0,1,2,...,9}에서 공집합이 아닌 임의의 부분집합을 생각해보자.
예를 들어 {1,3,5,9}라고 할 때 이 집합에 대응되는 감소하는 수는 무조건 1개이다.
(수를 감소하게 둬야하기 때문) 그렇기 때문에 감소하는 수는 2^10 - 1 = 1023개이고
미리 감소하는 수를 다 구한 후 정렬하면 N번째의 수를 편하게 알아낼 수 있다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1038_1.cpp

basic-algo-lecture/0x12/solutions/1038_1.cpp at master · encrypted-def/basic-algo-lecture

9를 예로 들면, 9 --> 4 ---> 2 --> 1 --> 0 이 된다. 이때, 9를 2로 나누면 나머지가 1이다. 즉 , 이진수의 2^0이 필요하다. 1을 2로 나누면, 나머지가 1이다. 따라서, 2^3자리가 필요하다. [0~9] 10개의 숫자 중에 특정 x개를 골라서, 감소하는 숫자의 경우의 수는 1023가지다. (2^10이 아닌 이유는 모든 수를 안 뽑는 경우는 포함시키면 안 된다.) 

 

9승	8승	7	6	5	4	3	2	1	2의0승
512	256	128	64	32	16	8	4	2	1