[프로그래머스] Summer/Winter Coding(2019) : 종이접기 (level 3) (c++)

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

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

 

 

#include <string>
#include <vector>

using namespace std;

/*
1                0
2        0       0       1
3    0   0   1   0   0   1   1
4  0 0 1 0 0 1 1 0 0 0 1 1 0 1 1
...
*/

void go(vector<int> &v, int depth, int n)
{
    if (depth == n)
    {
        return;
    }

    // n번째 수열은 0을 중앙에 두고 서로 대칭한다.
    v.push_back(0);
    for (int i = v.size() - 2; i >= 0; --i)
    {
        v.push_back(1 - v[i]);
    }

    go(v, depth + 1, n);
}

vector<int> solution(int n) {

    vector<int> answer;

    go(answer, 0, n);

    return answer;
}

 

 

그리 어려운 문제가 아니었는데 문제를 집중해서 읽지 않아 시간을 많이 소비했다 ㅜㅜ

 

종이를 접은 횟수 n이 매개변수로 주어질 때,
종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

- 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.

 

종이를 여러번 접었을 때 접히는 규칙을 수열로 나타내는 문제였다.

그러니까... 접힌 선에 포커스를 맞춰야지, 면에 집중하면 안된다는 뜻이다.

즉, n이 늘어갈수록 숫자열이 변화하는 규칙성을 찾으면 된다.

 

 

규칙을 찾을 땐 역시 그림으로 그려야..

종이를 반으로 접으니까, 대략 중앙을 기점으로 대칭성이 있을 거라고 추측할 수 있다. 혹시 모르니 숫자를 좀더 진행시켜 보자

 

 

 

중앙을 기점으로 대칭성이 있긴 한데, 좌/우의 숫자가 뒤집어져서 대칭되는 것 같다.

 

 

 

한번 더 진행해보니 위의 추측이 맞았다. 이제 구현으로 ㄱㄱ하자

 

 

따라서 이전까지의 배열에 가운데자리 0을 push하고,

그 이전의 수열을 뒤집어서 한번씩 더 push해주면 된다.

// n번째 수열은 0을 중앙에 두고 서로 대칭한다. (숫자를 뒤집어서)
v.push_back(0);
for (int i = v.size() - 2; i >= 0; --i)
{
    v.push_back(1 - v[i]);
}

go(v, depth + 1, n);