[BAEKJOON]백준 11727번 2xn 타일링 2 - DP

백준 11727번 2xn 타일링 2

백준 11727번 2xn 타일링 2

설명

타일로 채우는 경우의 수가 크게 3가지가 있다. n일 때 타일을 채우는 방법의 수를 f(n)이라고 하면,

1. f(n-1)에서 2x1 타일 1개를 놓는 경우
2. f(n-2)에서 1x2 타일 2개를 놓는 경우
3. f(n-2)에서 2x2 타일 1개를 놓는 경우

f(n-2)에서 2x1 2개를 놓는 경우를 생각 할 수도 있지만, f(n-1)에서 2x1 타일 1개를 놓는 경우와 겹친다.

코드

import sys, collections
input = sys.stdin.readline


class Solution:
    def tiling(self, n: int):
        dp = collections.defaultdict(int)
        dp[1], dp[2] = 1, 3
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]*2
        return dp[n]%10007

print(Solution().tiling(int(input())))