[BAEKJOON] 백준 17175: 피보나치는 지겨웡~ (C#)

문제 링크

https://www.acmicpc.net/problem/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 로 나눈 나머지를 출력한다.

 

 

 

통과한 답안

namespace _17175
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[51];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                dp[i] = (dp[i - 1] + dp[i - 2] + 1) % 1000000007;
            }

            Console.WriteLine(dp[n]);
        }
    }
}

 

이 문제는 피보나치 수를 구하는 문제가 아니라

재귀적인 방법을 사용하여 피보나치 수를 구하는 경우에

피보나치 수를 구하는 함수가 몇 번 호출되는지를 찾는 문제이다.

 

피보나치 수를 재귀적으로 구하는 방법을 생각해보면,

우선 주어진 조건에서 n이 2 미만인 경우에는 그대로 숫자를 출력하므로,

이는 호출 횟수가 1이다

즉, dp[0] = 1, dp[1] = 1

 

이후에 dp[2]부터 생각해보면,

dp[2]를 구하기 위해서 fibonacci(2)를 작동시키면 1회,

fibonacci(0) + fibonacci(1)을 수행하는 과정에서 각각 1회로

총 3회의 호출이 발생한다. 따라서 dp[2] = 3

 

dp[3]의 경우에는 dp[3]을 구하기 위해서 fibonacci(3)을 작동시키면 1회,

fibonacci(1) + fibonacci(2)를 수행하는 과정에서 1회와 3회로

총 5회의 호출이 발생한다. 따라서 dp[3] = 5

 

이를 정리해서 살펴보면,

dp[n]은 초기 호출 시에 1회와

fibonacci(n - 2)와 fibonacci(n - 1)을 구하는 과정에서

각각dp[n - 2], dp[n - 1]회의 호출이 발생한다.

즉, dp[n] = dp[n - 2] + dp[n - 1] + 1 의 관계를 구할 수 있다.