[프로그래머스] 종이접기

[프로그래머스] 종이접기

문제 링크

#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0); //초기값

    for(int i=2; i<=n; i++){
        vector <int> save = answer;

        answer.push_back(0);

        int idx = save.size() / 2;

        for(int j=0; j<save.size(); j++){
            if(j == idx){
                answer.push_back(!save[j]);
                continue;
            }else
                answer.push_back(save[j]);
        }
    }
    return answer;
}

n	색종이
1번	0
2번	001
3번	0010011
4번	001001100011011
5번	0010011000110110001001110011011

• 접다 보면 규칙이 생긴다
• 일단 n은 처음에 n-1이 그대로 반복된다.
• 그 후 0이 추가가 된다 (새로 접힌 부분)

• 그리고 이후도 그대로 반복 되지만
• n-1에서 접혔던 곳이 반대로 된다.
• 이 곳은 늘 중간에 위치하므로 그 인덱스만 반대로 바꿔주면 된다.