[python/파이썬] 백준 15624 피보나치 수 7

[문제 출처]

https://www.acmicpc.net/problem/15624

15624번: 피보나치 수 7

 

[문제 풀이]

재귀 함수를 사용하면 에러가 나오는 문제이다.

따라서 dp를 사용하여 문제를 풀었다.

결과를 출력할 때 문제에서 n번째 수를 1,000,000,007로 나눈 나머지 값을 출력하라고 되어 있는데

리스트에 다 저장하고 마지막에 결과를 나눈 나머지 값을 출력하는 방식으로 하면 메모리 초과가 나오기에

아래 코드처럼 리스트에 저장할 때 나눈 값으로 저장해줘야 한다.

import sys
input = sys.stdin.readline

n = int(input())

fibo = [0, 1]

for i in range(2,n+1):
    fibo.append((fibo[i-1] + fibo[i-2])%1000000007)

print(fibo[n])