2022.02.15

백준 1904 타일 01

#1904

N = int(input())
dp = [0]*(N+1)

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    dp[1] = 1
    dp[2] = 2
    for i in range(3,N+1):
        dp[i] = (dp[i-2] + dp[i-1])%15746
    print(dp[N])

점화식 자체는 피보나치수열과 같다.

거기에 문제에서 주어진 메모리 초과를 해결해주기 위해서

문제풀이 과정에서 나머지를 구해주면 된다