종이접기

https://programmers.co.kr/learn/courses/30/lessons/62049?language=cpp

프로그래머스 programmers

우선 오른쪽에서 왼쪽으로 무조건 접고 시작하므로, answer 벡터에서 가운데 값은 무조건 0임을 알 수 있다.

또한, 가운데를 기준으로 오른쪽, 왼쪽은 완벽히 포개어진다.(합쳐진다)

가운데를 기준으로 종이를 폈다, 접었다 할 수 있다.

따라서, 완벽히 포개어지므로(합쳐지므로),

∨∧ 의 합이 1이 되어야한다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0);
    if (n == 1) {
        return answer;
    }
 
    int idx = 0;
    for (int i = 1, len = 3; i < n; i++, len = 2*len + 1) {
        vector<int> temp;
 
        for (int j = 0; j < len; j++) {
            if (j < len / 2) {
                temp.push_back(answer[j]);
            }
            else if (j == len / 2) {
                temp.push_back(0);
            }
            else {
                temp.push_back(1 - answer[idx--]);
            }
        }
 
        answer = temp;        
        idx = answer.size() - 1;
    }
 
    return answer;
}
 
int main()
{
    cin.tie(0);
 
    vector<int> v = solution(10);
 
    for (auto i : v) {
        printf("%d ", i);
    }
 
    return 0;
}