3 x n 타일링 (lv2)

문제 설명

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

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

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

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

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

 우선, 제한사항의 경우의수를 10^9 가 넘는 수로 나눠서 출력하라는 문구부터 벌써 완전탐색은 절대로 아니겠구나, 하는 판단이 된다. 이전에 DP 유형을 연습하며 풀었던 "바닥 공사" 문항과 굉장히 유사하다는 생각이 들기도 하고, 무엇보다 가로길이 n만큼 블록을 놓을 수 있는 경우의 수를 구할 때 n 보다 작은 가로 길이만큼 놓는 경우의 수를 이용하므로 DP로의 접근이 유효하다고 판단 가능하다.

 만약 위 그림의 첫번째의 경우처럼, 블록을 늘어놓을때 맨 오른쪽 끝에 반드시 두칸을 완전히 차지하도록 놓는다면, 결국에 dp[i]는 dp[i-1]과 같을 것이다 (블록은 짝수개밖에 놓지 못하므로 i-2가 아닌 i-1로 두었다). 하지만 당연히 이게 끝이 아닌데, 오른쪽 두 경우 처럼 dp[i-1]을 직접적으로 가져오기 애매한 경우가 있다.

 그러나 두 경우 역시 위 그림처럼 블록을 차례로 놓다보면 i-1번째 의 경우 역시 i번째 겪었던 문제와 같은 문제가 발생한다는 사실을 알 수 있고, 이는 블록이 처음 놓인곳까지 반복된다. 따라서 다음과 같은 점화식을 세울 수 있다.

$$dp[i] = dp[i-1] + 2*{sum([dp[i-1],dp[i-2],...,dp[1],1])}$$

코드

def solution(n):
    dp = [0]*(n//2+1)
    dp[1],dp[2] = 3,11
    for i in range(3,len(dp)):
        dp[i] = dp[i-1] + 2*(sum([dp[i-j] for j in range(1,i)])+1)
    return dp[n//2] % 1000000007