[프로그래머스] 3 x n 타일링 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

 

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일로 세로의 길이가 3이고 가로의 길이가 n인 바닥을 채울 때, 직사각형을 채우는 방법의 수를 return하는 문제이다.

제한사항

• 가로의 길이 n은 5,000 이하의 자연수입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

풀이

프로그래머스의 2 x n 타일링의 연장선으로 dp문제이다. 점화식을 찾아 그 식을 함수에 대입하면 된다.

점화식을 구해보면,

 

✅ Code - 성공

def solution(n):
    answer = 0
    
    dp = [0] * (n + 1)
    dp[2], dp[4] = 3, 11
    
    if n % 2 != 0:
        return 0
    if n < 6:
        return dp[n]
    
    for i in range(6, n + 1, 2):
        dp[i] = (dp[i - 2] * 3 + sum(dp[2:i-2:2]) * 2 + 2) % 1000000007
    
    return dp[n]