[ 프로그래머스 종이접기 (Lv3) ] (C++)

프로그래머스의 종이접기(Lv3) 문제이다.

[ 문제풀이 ]

규칙을 찾고나면 굉장히 쉽게 해결할 수 있는 문제였지만, 규칙을 찾는 과정이 너무 어려웠던 문제이다.

규칙을 한번 같이 찾아보자.

먼저 종이를 한번 접으면 아래로 굴곡이 생긴 V자 모양이 생기게 된다. 즉 ! n = 1 일 때의 정답은 0이 된다.

n = 2 일떄를 보면, "0 0 1" 의 형태로 굴곡이 생기게 된다.

그럼 n = 1 일때와 n = 2일 때를 비교해서 규칙을 한번 생각해보자.

0

0 0 1

본인은 여기서 2가지 규칙을 생각해보았다.

1. n - 1의 값에서 뒤에 '0 1'을 추가시키는 것.

2. n - 1의 값 앞에는 '0' 을, 뒤에는 '1'을 추가시키는 것.

2가지 조건 모두 n이 1과 2일때는 적용이 된다.

그런데 n = 3일 경우를 보면 "0 0 1 0 0 1 1" 이 된다. 딱 봐도 위의 2가지 조건 모두 n = 3일때는 적용이 되질 않는다.

첫 번째 조건대로 한다면 0 0 1 + 0 1 이 되어서 0 0 1 0 1 이 되어야 하고,

두 번쨰 조건대로 한다면 0 0 0 1 1 이 되어야 하기 때문이다.

그래서 생각을 해보니, "n - 1의 각 원소들 사이사이에 0과 1을 왔다갔다 하는 값이 추가"되는 규칙을 찾을 수 있었다.

n = 1 일 떄는 '0'

n = 2 일 때는 '0 0 1' 인데, 이 '0 0 1'이 나오게 되는 과정을 보게되면

n = 1 인 원소 앞에 '0'을 추가하고, 그 뒤에는 '1'을 추가하는 것이다.

n = 3 일 때는 '0 0 1 0 0 1 1' 인데

n = 2 의 값인  0  0  1 에서 사이사이에 0과 1을 왔다갔다 하는 수를 넣어주는 것이다. 아래와 같이 !

  0  0  1

0  1  0  1

ㅡㅡㅡㅡㅡ

0 0 1 0 0 1 1

이렇게 n = 3이 완성될 수 있다. 이 규칙을 이용해서 문제를 해결하였다.

[ 소스코드 ]

#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 Num = 0;
        int Idx = 0;
        vector<int> Temp;
        while (Idx < answer.size())
        {
            Temp.push_back(Num);
            Temp.push_back(answer[Idx++]);
            Num = !Num;
        }
        Temp.push_back(Num);
        answer = Temp;
    }
    return answer;
}