[ 17175 ] [DP] 피보나치는 지겨웡~

문제 설명

---

문제

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

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 로 나눈 나머지를 출력한다.

---

풀이 과정

1. 아래에서부터 바텀-업 방식으로 진행
   • fibonacci(0)일때는 1번 호출하므로 dp[0] = 1
   • fibonacci(1)일때는 1번 호출하므로 dp[1] = 1
2. fibonacci(n >= 2) 일때는, fibonacci(n-1)을 호출하므로 fibonacci(n-1)번, fibonacci(n-2)를 호출하므로 fibonacci(n-2)번, 그리고 자기 자신까지 +1해주면 된다.
   • 즉, dp[i] = dp[i-1] + dp[i-2] + 1
3. 마지막으로 dp[n]을 1000000007로 나눈 나머지 값을 출력하면 된다.

---

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (n+1)
if n <= 1:
    print(1)
else:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2] + 1

    print(dp[n] % 1000000007)