백준(BOJ) 17175 - 피보나치는 지겨웡~ [Python]

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

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

문제

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.

int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  }  
  return fibonacci(n-2) + fibonacci(n-1);
}

위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.

입력

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

출력

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

 

"""
    17175 - 피보나치는 지겨웡~
    점화식 찾는건 쉽다
    함수 호출 횟수를 확인해보면
    0 : 1번
    1 : 1번
    2 : f(2) 1번, f(0), f(1) 1번씩 총 3번
    3 : f(3) 1번, f(1) 1번, f(2) 3번 총 5번
    4 : f(4) 1번, f(2) 3번, f(3) 5번 총 9번
    5 : f(5) 1번, f(3) 5번, f(4) 9번 총 15번
    즉 dp[i] = dp[i-2]+dp[i-1]+1 이 된다.

    마지막에 1000000007으로 나누기

"""

n = int(input()) # 입력할 n ( 0 <= n <= 50)
mod = 1000000007
dp = [i for i in range(n+2)] # 점화식 찾기
dp[0] = 1
dp[1] = 1

if n < 2 :
    print(1) # n이 2보다 작은 경우 0, 1 두가지 실제 호출 횟수는 1

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