[백준] 17175번. 피보나치는 지겨웡~

[백준] 17175번. 피보나치는 지겨웡~

내말그말

1. 문제

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

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

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

2. 입력

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

3. 출력

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

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

4. 풀이

• fibo(n) = fibo(n-1) + fibo(n-2)기 때문에 호출 횟수도 DP로 배열에 저장해서 쓸 수 있다. 단, 처음에 자기 자신을 한 번 호출하기 때문에 1을 더해주어야 한다.
• 점화식: fibo(n) = fibo(n-1) + fibo(n-2) + 1

5. 코드

#include <iostream>

using namespace std;

int fibo[51];

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
   
    int n;
    cin >> n;
    fibo[0] = 1;
    fibo[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        fibo[i] = (fibo[i - 2] + fibo[i - 1] +1) % 1000000007;
    }
    cout << fibo[n];
}