백준 알고리즘 1904번 01타일(python)

기본적인 다이나믹 프로그래밍 문제이다.

N = 1 -> 1개, N = 2 -> 2개, N = 3 -> 3개, N = 4 -> 5개, N = 5 -> 8개...

규칙을 보면 1, 2, 3, 5, 8, 13 ...인데 피보나치 수열이다.

a, b = 1, 1
for i in range(int(input())):
    a, b = b%15746, (a+b)%15746
print(a)