백준 1003번 - 피보나치 함수 (C#)

김보근·2025년 8월 1일

C#백준

백준

목록 보기

53/62

백준 1003번 - 피보나치 함수 (C#)

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

문제 설명

기존의 피보나치 함수는 다음과 같이 재귀적으로 정의된다.

int fibonacci(int n) {
    if (n == 0) {
        print("0");
        return 0;
    } else if (n == 1) {
        print("1");
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

이 함수를 호출했을 때 fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지를 출력하는 문제다.

처음 시도한 방식

처음엔 직접 함수를 재귀적으로 호출하면서 fibonacci(0)과 fibonacci(1)이 몇 번 호출되는지를
카운트하는 방식으로 풀려고 했다. 함수 안에서 호출될 때마다 count0++, count1++을 해주는 식이다.

하지만 이렇게 하면 입력이 커질수록 재귀 호출 횟수가 기하급수적으로 증가해서
시간 초과가 발생한다. 예를 들어 fibonacci(30)을 계산하는 데만도 수십만 번의 호출이 일어난다.

해결 방법 - DP로 호출 횟수 미리 계산하기

매번 재귀 호출을 할 필요 없이,
fibonacci(n)을 호출했을 때 fibonacci(0)과 fibonacci(1)이 몇 번 호출되는지를
미리 DP 테이블에 저장해두면, 입력을 받을 때마다 바로 출력할 수 있다.

dp[n, 0]: fibonacci(n)을 호출했을 때 fibonacci(0)이 호출된 횟수
dp[n, 1]: fibonacci(n)을 호출했을 때 fibonacci(1)이 호출된 횟수

피보나치 정의에 따라 호출 횟수도 아래와 같은 점화식을 따른다:

dp[n, 0] = dp[n - 1, 0] + dp[n - 2, 0];
dp[n, 1] = dp[n - 1, 1] + dp[n - 2, 1];

작성한 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {

        static void Main()
        {
            int t = int.Parse(Console.ReadLine());
            int[,] dp = new int[41, 2]; // 0~40까지, [i, 0]은 0의 호출 수, [i, 1]은 1의 호출 수

            // 초기값
            dp[0, 0] = 1; dp[0, 1] = 0; // fibonacci(0)은 0 한 번
            dp[1, 0] = 0; dp[1, 1] = 1; // fibonacci(1)은 1 한 번

            // DP로 피보나치 호출 횟수 저장
            for (int i = 2; i <= 40; i++)
            {
                dp[i, 0] = dp[i - 1, 0] + dp[i - 2, 0];
                dp[i, 1] = dp[i - 1, 1] + dp[i - 2, 1];
            }

            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine($"{dp[n, 0]} {dp[n, 1]}");
            }
        }
    }
}