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

문제출처

https://programmers.co.kr/learn/courses/30/lessons/62049

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

 

문제풀이

규칙을 찾아내면 쉬운 문제. 규칙을 처음에 찾으려고 직접 종이를 접어가면서 풀이했다. 직접 종이를 접어가며 나오는 출력값을 적어가는 도중 0을 대칭으로 어떤 연산이 일어나는 걸 알아차렸다. 

즉 n이 3인경우 0 0 1 -> 0 0 1 0 0 1 1 으로 바뀌는데 0 0 1 뒤에 0을 붙이고 n이 2일때의 값을 뒤집어서 1이면 0, 0이면 1을 넣어주면 된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0.cpp

sw93/algorithm

#include <string>
#include <vector>

using namespace std;
/*
* 규칙 
* 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 = 2 -> 3이 될때 0 0 1과 0 1 1 을 보면 기존 0은 1로 1은 0으로 바뀌고 가운데 0이 끼는 것을 알 수 있음
* n = 3 -> 4가 될때도 기존 3인 값에 0이 추가 되고 역순으로 0은 1로 1은 0으로 바뀜
*/
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0);
    if (n == 1) return answer;
    for (int i=2; i<=n; i++) {
        vector<int> temp = answer;
        answer.push_back(0);
        for (int j=temp.size()-1; j>=0; j--) {
            if (temp[j] == 0) answer.push_back(1);
            else if (temp[j] == 1) answer.push_back(0);
        }
    }
    
    return answer;
}