[Programmers] 종이접기 - travelbeeee

---

[ 알고리즘풀이 ]

규칙만 찾으면 구현은 간단한 문제입니다.

n = 1 [ 0 ]

n = 2 [ 0 0 1 ]

n = 3 [ 0 0 1 0 0 1 1 ]

n = 4 [ 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 ]

n = 5 [ 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 ]

n = k 일 때, 파란색 부분을 보시면 n = k - 1일 때와 동일한 것을 파악할 수 있습니다. 빨간색 부분도 자세히 보면 n = k - 1 일 때에서 검은색 부분인 '0' 만 '1'로 바꿔주면 나머지 부분은 동일한 것을 확인할 수 있습니다. 따라서, 파란색 부분을 의미하는 left 와 빨간색 부분을 의미하는 right 를 갱신해나가며 답을 구할 수 있습니다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;

    string left = "0", right = "1";
    for(int i = 2; i <= n; i++){
        string ltmp = left + '0', rtmp = left + '1';
        ltmp = ltmp + right; rtmp = rtmp + right;
        left = ltmp; right = rtmp;
    }
    for(int i = 0; i < left.size(); i++){
        answer.push_back(left[i] - '0');
    }

    return answer;
}

---