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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

규칙성을 찾아서 해결하는 문제이다. 처음엔 규칙이 잘 보이지 않았지만 차분하게 생각해보니 간단한 규칙을 발견할 수 있었다.

풀이

종이를 접게 되면 접은 선의 개수는 홀수가 된다.
n번 접은 종이의 선들 중에서 가운데 선을 기준으로 왼쪽의 선들은 n-1번 접은 종이의 선의 모양과 같다는 것을 알 수 있다. 가운데 있는 선은 제일 처음 반을 접을 때 생기는 선이므로 결국 가운데 선을 중심으로 원점 대칭 꼴이라는 것을 알 수 있다.

예시로 확인해보면 3번 접은 경우는 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1와 같은데, 확인해보면 가운데 0을 중심으로 0과 1이 반전되어있다는 것을 알 수 있다.

코드

#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++){
        int size = answer.size();
        answer.push_back(0);
        for(int j=size-1; j>=0; j--)
            answer.push_back(!answer[j]);
    }
    return answer;
}