백준 1904 01 타일 - Python

 

출처 : https://www.acmicpc.net/problem/1904

1904번: 01타일

import sys 
input = sys.stdin.readline
n = int(input())
a = [0]*1000001

a[1],a[2] = 1, 2
for i in range(3,n+1):
    a[i] = (a[i-2]+a[i-1])%15746

print(a[n])

풀이 : 

그래서 피보나치 문제임을 확인했고 

 

이게 재귀함수를 사용해서 풀었었는데 그렇게 풀면 메모리초과가 나기 때문에 위 풀이 처럼 풀어야한다.

 

간단하므로 넘어간다ㅣ