[Python | 프로그래머스 | Lv_2] 2 x n 타일링

😉 아이디어

1. 특이케이스 생성에 집중 👉 _!n > 2 이상부터는 특이케이스 없음!_
2. _!n = 1 or 2!_의 특이케이스로 점화식 생성

😉 풀이

def solution(n):
    answer = 0
    
    # n = 1 -> 1 (1)
    # n = 2 -> 2 (1)
    # n = 3 -> 3 (0)
    # n = 4 -> f(3) * 1 + f(2) * 1 + f(1) * 0
    # n = 5 -> f(4) * 1 + f(3) * 1 + f(2) * 0 + f(1) * 0
    
    # 패턴: [0, 1, 1, 0, 0, ...]
    
    dp = [0, 1, 2, 3]
    pattern = [0, 1, 1, 0, 1, 0]
    isZero = True
    
    for i in range(4, n + 6):        
        val = (dp[i - 1] + dp[i - 2]) % 1_000_000_007
        dp.append(val)
            
    return dp[n]

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12900