[프로그래머스] 아방가르드 타일링 (DP)

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

프로그래머스

 

분석

2를 표현하는 방법

3을 표현하는 방법

DP(10) = DP(9) + 2*DP(8) + 5*DP(7)
+ 2*DP(6) + 2*DP(5) + 4*DP(4)
+ 2*DP(3) + 2*DP(2) + 4*DP(1)
+ 2
 DP(n)을 구하는데 DP(n-4)부터는 반복되는 구간이 나타나므로 DP(n+3)에서 DP(n)을 빼서 하위 구간을 삭제

DP(13) - DP(10) = DP(12) + 2*DP(11) + 5*DP(10) + DP(9) - DP(7)
이 식을 바꿔보면 DP(13) = DP(12) + 2*DP(11) + 6*DP(10) + DP(9) - DP(7)

즉, 아래와 같은 점화식을 세울 수 있다.
DP(x) = DP(x-1) + 2*DP(x-2) + 6*DP(x-3) + DP(x-4) - DP(x-6)

 

풀이

def solution(n):

    dp=[0]*100001
    
    dp[1]=1
    dp[2]=3
    dp[3]=10
    dp[4]=23
    dp[5]=62
    dp[6]=170
    
    if n>6:
        for i in range(7,n+1):
            dp[i] = (dp[i-1] + dp[i-2]*2 + dp[i-3]*6 + dp[i-4] - dp[i-6]) % 1000000007

    return dp[n]