파이썬 백준 1904 01타일

n = int(input())
list = [0, 1, 0]
for i in range(n) : 
    list[2] = (list[0] + list[1]) % 15746
    list[0], list[1] = list[1], list[2]
print(list[min(n, 2)])

IDEA

길이 n의 수열은 길이 n-1의 수열에 1을 붙이거나, 길이 n-2의 수열에 00을 붙여서 만들어진다.

점화식으로 나타내면 f(n) = f(n-1) + f(n-2)인 피보나치 수열이다.

n-2 이전의 값은 f(n)을 구하는데 필요없으므로, dp는 3칸만 있으면 된다.