[WEEK04] 25일차. 01타일

01타일

규칙을 잘 찾으면 피보나치와 동일한 규칙을 가진 것을 발견할 수 있다.
DP를 활용해서 코드를 작성했는데, 나머지 연산을 마지막에 한 번 했더니 메모리 초과가 발생했다.

계산 과정에 계속해서 나머지 연산을 해주면 메모리 초과가 발생하지 않는다.

코드

import sys

inp = sys.stdin.readline

n = int(inp())

d = [0] * (1000001)
d[1] = 1
d[2] = 2

def tile(n):
    for x in range(3, n+1):
        d[x] = (d[x-1] + d[x-2])%15746
    return d[n]

print(tile(n))