[dp] 11333 4xn 타일링 (파이썬)

문제

icpc 왕국에는 아주 못된 왕 유빈이가 있었다.

유빈이에게는 4×n 크키의 카펫이 하나 있었다.

유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다.

여러분이 신하들을 도와서 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를  구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 수 T가 주어진다. (1 <= T <= 100)

그 다음 T개의 줄에는 카펫에 가로 길이 N이 주어진다. (세로 길이는 4) (1 <= N <= 10,000)

출력

각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.

• 세로는 4로 고정 되어 있음
• 1*3과 3*1로 세로의 길이 4를 만들려면 맨 윗변이나 아랫 변에 1*3이 무조건 하나는 있어야 함
• 1*3과 3*1로 만들 수 있는 가로의 길이 경우의 수를 모두 구한다.
  • 여기서 생각 해 볼 수 있는 것은 1*3과 3*1로 가로의 길이를 채우는 것이므로 dp[n]은 dp[n-1]과 dp[n-3]한테 영향 받을 것.
  • dp[n-1]에서 3*1을 하나씩 세우거나, dp[n-3]에서 1*3을 설치하는 것 
• 세로의 길이 4를 만들려면 맨 윗변이나 아랫변에 1*3을 설치하는 거니 가로의 길이(n)이 3의배수+1 일 때 경우의 수가 [n-1] 2배씩 증가함
• 3의배수+1이 아닐 때는 dp[n-1]에서 하나씩 그냥 세우면 됨

따라서,

N이 3의 배수 +1 이라면, dp[n] = dp[n-1]*2 + dp[n-3]

그 외 경우에는 dp[n] = dp[n-1]+dp[n-3]

 

def solution(n):
    answer = 0
    if (n % 3 != 0):
        return 0
    dp = [0]*(n+1)
    dp[1] = 2
    dp[2] = 2
    dp[3] = 3
    for i in range(4, n+1):
        if (i % 3 == 1):
            dp[i] = dp[i-1]*2 + dp[i-3]
        else:
            dp[i] = dp[i-1]+dp[i-3]

    return dp[n] % 1000000007


T = int(input())
for i in range(T):
    N = int(input())
    print(solution(N))