[백준/Python3] 11726번 2xN 타일링

문제

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

풀이

• 점화식
  - dp[n] = dp[n - 1] + dp[n - 2]
  - 블록을 가로로 놓을 경우에는 n - 1까지 블록을 놓으므로 n - 2까지 블록이 놓여진 경우의 수를 합해야 한다
  - 블록을 세로로 놓을 경우에는 n - 1까지 블록이 놓여진 경우의 수를 합해야 한다

코드

from sys import stdin

n = int(stdin.readline())

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

print(dp[n - 1])