programmers [C++] : 종이접기

programmers.co.kr/learn/courses/30/lessons/62049#

코딩테스트 연습 - 종이접기

문제 설명

---

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다. 종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열을 완성하시면 됩니다.

 

접근 방법

---

저는 4번까지 배열을 구해보며서 규칙을 발견하였습니다~

 

코드

---

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> ans;
    int prev,k=0;
    while(k!=n){
        if(k==0){ans.push_back(0);}
        else{
            prev=ans.size();
            ans.push_back(0);
            for(int i=prev-1;i>=0;i--){
                if(ans[i]==0)ans.push_back(1);
                else ans.push_back(0);
                
            }
            //ans.push_back(0);
        }
        k++;
    }
    return ans;
}

funny algorithm 0_<