CodeDrive

문제:

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n=2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 종이에 접은 흔적이 생기게 됩니다.

V 모양이 생긴 부분은 점선(0)으로, ㅅ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

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

풀이방법:

이 문제는 종이접기 수열을 사용하는 문제이다. 종이접기 수열이란 이 문제처럼 종이를 일정한 방향으로 접었을 때 생기는 굴곡에 대한 수열이다. 

이 문제처럼 오른쪽에서 왼쪽으로 접는 경우에는 가운데가 0으로 고정되어서 수열이 생성된다.

1 ->  0

2 ->  0 + 0 + 1

3 ->  0 + 0 +1 + 0 +0 + 1+ 1

4 -> 001+0+011 + 0 + 001+1+011

5 -> 0010011+ 0 + 0011011 + 0 +0010011 + 1 + 0011011

....

1, 2, 3에서는 규칙을 찾기 어렵지만 4부터는 규칙을 찾을 수 있다.

가운데 0을 기준으로 이전 단계의 모양이 반복되는 것을 알 수 있다. 가운데 0을 기준으로 했을 때 왼쪽은 이전단계의 중간이 0인 경우 오른쪽은 이전단계의 중간이 1인 경우이다. 따라서 1, 2의 경우에는 예외처리로 두어서 답을 반환하도록 하고, 3부터는 반복문을 통해서 규칙을 생성하도록 하였다.

문제링크:

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