https://www.acmicpc.net/problem/11727

초고

n = int(input())
dp = [0 for _ in range(1001)]
dp[1] =1
dp[2] =3
if n>2:
    for i in range(3,n+1):
        dp[i] = (dp[i-1] + 2*dp[i-2]) %10007
print(dp[n])

2xn 타일링 1 번 문제의 변형이다.

https://velog.io/@mpfo0106/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-BOJ-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81

기존에서 2x2 타일이 추가되었는데 총 3가지 경우의 수다.

• 2x1 타일을 수직으로 배치하여 2x(n-1) 직사각형을 남김. dp[n-1]
• 1x2 타일을 가로로 놓고 2x(n-2) 직사각형을 남김. dp[n-2]
• 2x(n-2) 직사각형을 남기는 2x2 타일을 남김. dp[n-2]

dp[i] = dp[i-1] + 2*dp[i-2]