프로그래머스 - 종이접기

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

접근

개인적으로 많이 마주치지 못한 유형이라 신선했습니다.

이런 스타일의 문제는 규칙성 발견이 주가 된다고 생각하여 분할 정복으로 풀어봤습니다.

지문 그대로 계속 실행하다보면 뭐가 0 이고 뭐가 1인지 햇갈립니다.

그래서 모두 종이 1장을 접는 경우로 분할해봅시다.

1장을 오른쪽을 잡고 왼쪽으로 접는다면 점선(0)이 생깁니다.

이때 다시 한번 더 접는것은 종이 2장을 포개놓고 접는것과 동일하며

포개진 아래쪽 종이는 정상적인 방향, 위쪽 종이는 반대 방향으로 접히므로

0 0 1 이 됩니다.

계속 이렇게 하다보면 접히는 중간선을 중심으로 좌측에 0 우측에 1이 생긴다는 규칙을 발견할 수 있습니다.

구현이야 저처럼 dfs해도 되고, 비트마스크나 다른 방법을 사용하면 조금더 효율적일것 같기도 합니다.

다음은 코드 전문입니다.

def dfs(depth,num,ans):
    if depth >= folding_num:
        ans.append(num)
        return
    else:
        dfs(depth+1,0,ans)
        ans.append(num)
        dfs(depth+1,1,ans)


def solution(n):
    global folding_num
    folding_num = n
    answer = []

    dfs(1,0,answer)
    return answer