[백준_1904] 01타일 python

이런 문제를 마주할 때마다

귀납적으로 이런 규칙이 있구나하고 발견은 하겠으나

연역적으로 왜 이런 규칙이 나오는지는 잘 모르겠다.

처음에 나눈 값으로 저장 안했다가 맥북 메모리 박살날뻔했다.

# dp 설계
dp = [
    0 for _ in range(1000001)
]

# dp 초기설정
dp[1] = 1
dp[2] = 2

# dp 채워넣기
for i in range(3, 1000001):
    dp[i] = (dp[i-2] + dp[i-1]) % 15746

# n 입력
n = int(input())

# 출력
print(dp[n] % 15746)