[BOJ] 11727 / 2×n 타일링2 / Python

Algorithm PS/BOJ

migrationArc 2021. 5. 10. 10:45

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

11726 / 2 X n 타일링 문제에 조건이 추가되었다.

N = 1 -> 1
N = 2 -> 3
N = 3 -> 5
N = 4 -> 11
N = 5 -> 21

추가된 조건의 경우의 수는 위와 같았다.

점화식: dp(N) = dp(N-1) + 2*dp(N-2)

Tabluation 을 이용한 풀이는 다음과 같다.

N = int(input())
dp = [0, 1, 3] + [0] * N

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