[Programmers] 종이접기

 

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

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

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

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

 

 

#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] 드래곤커브