백준 1904 파이썬 python : 01타일 @@황소처럼 우직하게@@ dp설명, 메모리초과, 런타임에러

dp[n] = dp[n - 1] + dp[n - 2]

에요.

왜냐면

1을 붙이거나 00을 붙이기 때문이에요

1을 1칸이니까 dp[n - 1] 빼기 1이고,

00은 2칸이니까 dp[n - 2] 빼기 2에요.

.

그리고 n == 1 일때 예외처리 해주시고, (런타임에러)

% 까먹지 마시고 (메모리초과)

n = int(input().strip())

dp = [0] * (n + 1)
if n == 1:
    print(1)
    exit()
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 15746

print(dp[-1] % 15746)