[백준/python] 15624번: 피보나치 수 7

문제

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

15624번: 피보나치 수 7

---

문제 요약

n이 주어졌을 때 n번째 피보나치 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

코드

import sys
input = __import__('sys').stdin.readline

n = int(input())

dp = [0, 1]

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

print(dp[n])

---

코드 설명

N의 범위가 0부터 1,000,000이므로 큰 피보나치 수를 구해야한다.

 

파이썬은 기본적으로 1000번까지의 재귀 호출만을 허용한다.

따라서 메모이제이션을 활용한 재귀 함수 코드로는 런타임에러가 발생한다.

+ 메모이제이션이란 불필요하게 중복된 계산을 피하기 위해 계산된 결과값을 테이블에 저장하는 것이다.

 

sys.setrecursionlimit() 함수를 이용하여 최대 재귀 깊이를 더 크게 설정해주어도 메모리 초과가 발생한다.

 

1. 재귀 함수와 메모이제이션 대신 리스트 dp에 먼저 피보나치 수열의 첫 번째, 두 번째 값을 저장하였다.

 

2. 반복문과 append함수를 통해 dp[i]에 피보나치 수열의 i번째 수를 1,000,000,007로 나눈 나머지값을 추가한다.

 

3. dp의 i번째 수를 출력한다.