import sys
input = sys.stdin.readline
n=int(input())
arr=[0,1,2]#n: 0 1 2
for i in range(3,n+1):
arr.append(arr[i-1]+arr[i-2])
print(arr[n]%15746)
메모리 초과라는 결과가 나왔다.
https://www.acmicpc.net/board/view/72658 해당 링크의 답변을 참고하여 수정하였다.
파이썬의 정수형이 고정 메모리가 아니라는 것을 알게 되었다.
import sys
input = sys.stdin.readline
n=int(input())
arr=[0,1,2]#n: 0 1 2
for i in range(3,n+1):
arr.append((arr[i-1]+arr[i-2])%15746)
print(arr[n])
접근 방법
f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8
로 f(n)=f(n-1)+f(n-2)
라는 식이 성립함을 알 수 있다. 따라서 해당 값을 계산 후 15746로 나눈 값을 배열에 추가해주면 된다.