33 lines
596 B
Python
33 lines
596 B
Python
# 2xn 타일링
|
|
|
|
import sys
|
|
|
|
input = sys.stdin.readline
|
|
|
|
def solution():
|
|
n = int(input().rstrip())
|
|
|
|
MOD = 10007
|
|
|
|
dp = [0] * (n+1)
|
|
dp[0] = 1
|
|
dp[1] = 1
|
|
|
|
for i in range(2, n+1):
|
|
dp[i] = (dp[i-1] + dp[i-2])%MOD
|
|
|
|
print(dp[n])
|
|
|
|
return
|
|
|
|
|
|
solution()
|
|
|
|
"""
|
|
걸린 시간: 6분
|
|
|
|
시간 복잡도: dp 테이블 n개 채우면 O(n)이다.
|
|
|
|
해설: 현재 보는 칸이 생겼을 때 1x2를 넣으려면 i-1칸까지 차있는 상태에서 넣으면 되고, 2x1을 넣으려면 i-2칸까지 차있는 상태에서 넣어야 한다.
|
|
따라서 dp[i-1] + dp[i-2]이다.
|
|
""" |