[BOJ/백준] 11727 - 2×n 타일링 2 (Python)

문제

문제링크

2*n 크기의 직사각형을 1*2(가로타일), 2*!(세로타일), 2*2(정사각형 타일) 타일로 채우는 방법의 수를 10007로 나눈 나머지를 구하라.

 

풀이

[BOJ/백준] 11726 - 2×n 타일링 (Python)

[BOJ/백준] 11726 - 2×n 타일링 (Python)

대부분의 풀이는 위 링크와 같다.

정사각형 타일을 맨 끝에 채우는 경우는 가로 타일을 채운 경우와 같다.

따라서 dp[n-2]이므로, dp[n]=(dp[n-2]+dp[n-1])+dp[n-2]가 된다.

 

코드

import sys
input=sys.stdin.readline

n=int(input())
dp=[0]*(n+1)

if n==1:
    print(1)
else:
    dp[1],dp[2]=1,3
    for i in range(3,n+1):
        dp[i]=2*dp[i-2]+dp[i-1]
    print(dp[n]%10007)