[백준] 1904 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

N = int(input())
dp = [0, 1, 2] + [0] * (N - 2)
for i in range(3, N + 1):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[N])

피보나치 수열인것같아서 넣었는데 메모리 초과가 떴다.

범위를 확인해보니 최대범위는 1,000,000이 되는데 피보나치 수열은 일정이상만 가도 수가 많이 커져서 메모리를 많이 잡아먹는다. 

dp에 할당할때 나머지값을 넣어줘서 해결하였다.