[Programmers] 종이접기

 

[문제 설명]

 

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

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

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

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

위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

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

 

 

[풀이 과정]

 

우선... '위 그림에서'라면서 그림은 보이지 않는다... 뭐.. 실은 문제를 이해하는데에는 지장이 없어서 아무래도 좋다.

 

고등학생때 확률과 통계 문제를 많이 풀어본 사람이라면 이런 문제를 어떻게 접근해야 하는지 쉽게 감이 올것이다.

 

수열이 있고, 규칙성이 잘 보이지 않는다면 일단 나열하라, 그러면 보일것이다.

 

n = 1  [0]

n = 2  [0, 0, 1]

n = 3  [0, 0, 1, 0, 0, 1, 1]

 

반으로 접어 굴곡을 만들고 또 반으로 접는다면 굴곡과 굴곡 사이에 또 굴곡이 생길 것이다.

 

n = 2 를 예로 들자면 [0, 0, 1]  각각의 요소 사이에 0 과 1이 번갈아 가며 삽입하면 n = 3 가 되지 않는가?

 

n = 2  [0, 0, 1]

n = 3  [(0삽입) 0 (1삽입) 0 (0삽입) 1 (1삽입)] = [0, 0, 1, 0, 0, 1, 1]

 

문제 해결의 키는 수열의 규칙성을 발견할 수 있는가? 이를 물어 보는 듯 하다.

 

규칙성이 없는 문제로 출제되지 않는다. 나열해가며 규칙성을 찾고자 노력한다면 발견할 수 있다.

 

또한 알고리즘으로는 동적 프로그래밍을 묻는듯 하다. n = 5 를 찾고자 한다면 n =1,2,3 은 필요하지 않다.

 

일회성으로 사용하고 초기화시켜 최적화하자.

 

def solution(n):
    if n == 1:
        return [0]
    
    before = '0'
    for _ in range(n-1):
        answer = []
        for i in range(0,len(before)):
            if i % 2 == 0 :
                answer.append('0')
                answer.append(before[i])
            else:
                answer.append('1')
                answer.append(before[i])
        answer.append('1')

        before = "".join(answer)[:]
        
    return list(map(int, answer))