프로그래머스 알고리즘 Lv4 3 x n 타일링

문제 출처 https://programmers.co.kr/learn/courses/30/lessons/12902?language=python3

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

-프로그래머스 문제 설명 中

def solution(n):
    m=n//2
    d=[1,3]
    if m<=1:return d[m]
 
    for i in range(2,m+1):
        d.append(d[i-1]*3+sum(d[:i-1])*2)
    return d[m] % 1000000007

내 풀이는 위와 같다. 재귀함수로 접근하려고 했더니 모든 케이스에서 시간 초과가 뜨자 조금 고민후 리스트 형식으로 접근하기로 했다.

n이 홀수인 경우는 성립할 수가 없으니 2로 나누어 보기 편하기 만들고 시작했다.

d[i-1]*3의 경우 d[i-1]에서 옆에 3개의 경우의 수를 추가하는 것이니 매우 쉽다.

그 밑 부분은 중복없이 정확히 세는 방법을 조금 오래 고민했다.

이런식으로 이웃과 작대기를 공유하는 케이스가 헷갈리게 만드는데,

n=8인 경우를 예를 들면, 맨 마지막은 d[i-1]*3 로 포함되어 있고, 위에서부터 우측 8, 6, 4칸은 쭉쭉 이어져 있는 경우가 위, 아래 두 가지씩. 좌측은 이미 계산되어있는 d 리스트에서 꺼내서 사용한다. 그렇기 때문에 실제로는 없는 n=0을 1로 편의상 설정한 것이다.