[dp/백준] 1904번: 01타일

-문제:https://www.acmicpc.net/problem/1904

-정답풀이

길이 별로 갯수를 구해보면 피보나치 수열을 이룬다

정답 출력할 때 15746으로 나누는 거 잊지말기!! 

값 삽입할 때 나눈 값을 넣어야 메모리 초과가 발생하지 않는다 

 

n=int(input())
dp=[1,2]

for i in range(2,n):
    dp.append((dp[i-1]+dp[i-2])%15746)
    
print(dp[n-1])