[Programmers] 종이접기

 

*BOJ의 드래곤커브와 비슷한 규칙으로 풀이하며 된다. 

*n번 접을 때의 배열 사이즈는 2^n -1이다. 

*가장 중앙값은 항상 [0] 이고 ((V) 로 접힐 수 밖에 없는 부분이니까)

0부터 mid-1 의 값들과 mid+1~2^n-2 까지의 값들은 반대로 대칭된다. (1-> 0 / 0->1)

 

 

?

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

#include <string> #include <vector> #include <iostream> #include <cmath> using namespace std;   vector<int> solution(int n) {     vector<int> answer;     //정중앙을 중심으로 대칭     int size = pow(2, n)-1;     vector<int> res(size);     res[0] = 0;     for (int i = 1; i < n; i++) {         int size = pow(2, i+1)-1; //현재 사이즈         int prev = pow(2, i) -1;                   res[prev] = 0;         int idx = prev;         for (int j = prev-1; j >= 0; j--) {             res[++idx] = 1-res[j];         }     }          answer = res;           return answer; }

 

<어려운 버전>

2019/08/06 - [BOJ/C++] - [BOJ] 드래곤커브

[BOJ] 드래곤커브