[c++] 백준 1038 - 감소하는 수(비트마스크, brute force)

0. [c++] 백준

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

1. 풀이

이번 문제를 풀면서 정말 감탄할만한 코드를 마주하였다. BaaaaaaaaarkingDog님이 짜놓은 코드였었는데, 보면 이 문제를 너무나 간결하게 풀이했다는 것을 느낄 수 있었다.

뭐, 이거보다 더 좋은 코드가 있기는 힘들 것 같을정도였다.

풀이하자면, 

(9,8,7,6,5,4,3,2,1,0)의 수의 위치는 우선적으로 고정이 되어있다 가정하자.

(0,1,1,0,0,1,0,0,0,1)의 경우라면

(  8,7,     4,      0)의 출력이 나오게 되는 것이다.

이런식으로 나오게 되는 수는 선택하거나 선택하지 않는 2가지의 경우의 수, 2^10에 아무것도 선택하지 않는 1가지의 경우를 제외한, 1023개의 경우가 발생하는데,

이 발생을 (% 2)를 활용해 2진수로 치환하여 간단하게 배열을 만들어 저장하고, sort를 활용해 정리를 끝낸 후 원하는 순서의 수를 꺼내오기만 하면 되는 방식의 풀이였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<iostream> #include<vector> #include<algorithm>   typedef unsigned long long ull;   std::vector<ull> dec_num;   void downSizeingNum(int N) {     if (N > 1022) {         std::cout << "-1" << std::endl;         return;     }              for (int i = 1; i <= 1023; i++) {         ull num = 0;// i에 대응되는 감소하는 수         int tmp_i = i;         for (int idx = 9; idx >= 0; idx--) {             if (tmp_i % 2 == 1)                 num = 10 * num + idx;             tmp_i /= 2;         }         dec_num.push_back(num);     }     sort(dec_num.begin(), dec_num.end());     std::cout << dec_num[N] << std::endl; }   int main() {     int N;     std::cin >> N;     downSizeingNum(N);       return 0; } Colored by Color Scripter

cs

3. 참고

https://blog.encrypted.gg/142

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!