[프로그래머스 파이썬] 3xn 타일링

일단 해볼게·2023년 2월 12일
0

프로그래머스

목록 보기
30/106

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

정답 코드

# 3 x n 타일링

def solution(n):
    dp = [0] * (n + 1)
    dp[2] = 3
    dp[4] = 11

    for i in range(4, n + 1, 2): # 시작 : 4, 끝 : n + 1, 2씩 증가
        dp[i] = dp[i - 2] * 3 # 1번
        
        for j in range(i - 4, -1, -2): # 시작 : i - 4, 끝 : -1, -2씩 감소
            dp[i] += dp[j] * 2 # 2번
        
        dp[i] = (dp[i] + 2) % 1000000007 # 3번, 나머지 계산
    
    return dp[n]

점화식

예시 (n = 8)

<1번>
dp[8] = dp[8 - 2] * 3

<2번>
dp[8] += dp[4] 2 + dp[2] 2

<3번>
dp[8] += 2

참고
https://dev-note-97.tistory.com/182

profile
시도하고 More Do하는 백엔드 개발자입니다.

0개의 댓글