3 x n 타일링 (DP)

프로그래머스

 

분석

(현재 경우의 수) = (이전 단계의 경우의 수) x (n = 2일 때 경우의 수) + 2 

dp[n]
= dp[n-2]*dp[2] + dp[n-4]*2 + dp[n-6]*2 + ... dp[2]*2 + 2
= dp[n-2]*3 + dp[n-4]*2 + dp[n-6]*2 + ... dp[2]*2 + 2

2를 더하는 이유 : 아래와 같은 새로운 모양의 타일이 생김

 

풀이

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

 

def solution(n):
    answer = [0,3,11]
    index = int(n/2)
    if n % 2 != 0: return 0
    if index < 3: return answer[index]

    for i in range(3, index+1):
    	# answer[i:j] -> answer에서 index가 i인 원소부터 j-1인 원소까지의 sub-array
        answer.append((3*answer[i-1]+sum(answer[1:i-1])*2+2)%1000000007)

    return answer[index]

 

 

프로그래머스 - 3xn 타일링 풀이 (python3)