[python/파이썬] 백준 17175 피보나치는 지겨웡~

[문제 출처]

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

17175번: 피보나치는 지겨웡~

 

[문제 풀이]

dp[i] 는 dp[i-1] 와 dp[i-2]의 합보다 1 큰 수로 정해진다.

fibonacci(n)을 호출했을 때 1혹은 0이 나올 때까지 fibonacci(n-1)과 fibonacci(n-2)를 호출한다.

따라서 fibonacci(n)를 호출한 횟수 1과 fibonacci(n-1)을 호출했을 때 fibonacci 호출 횟수인 dp[n-1]과 

fibonacci(n-2)을 호출했을 때 fibonacci 호출 횟수인 dp[n-2]을 더해줘야 한다. 

import sys
input = sys.stdin.readline

n = int(input())

dp = [1 for _ in range(n+1)]

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

print(dp[n])