문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우

• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

풀이

def solution(n):
    
    # dp[i] i=n일때 경우의 수 
    # dp[1] = 0
    # dp[2] = 3
    # dp[3] = 3
    # dp[4] = 11
    # dp[5] = 11
    # dp[6] = 33+2*2  4=1, 6=2, 8=3 (n//2)-1
    # dp[n] = dp[n-2]**3+2 ?
    if n == 1: 
        return 0
    if n == 2 :
        return 3
    if n == 3: 
        return 0
    
    dp = [0]*(n+1)
    dp[0] = 1
    dp[2] = 3
    
    s = dp[0]
    for i in range(4, n+1, 2):
        
        dp[i] = dp[i-2]*3+2
        
        for j in range(i-4, 0, -2):
            dp[i]+=2*dp[j]
            
        dp[i] = (dp[i])%1000000007
        
    
    return dp[n]

이해가 잘 안되서 다른 사람 풀이를 봤다.

점화식을 유도하는 과정이나 도형에 대한 수학적 능력이 많이 필요하다. 3*3 +2 까지는 직관적으로 유도했는데 그 너머가 잘 안됐다. 

직접 그려서 해결해봐야 하는 것 같다.