백준 24416 피보나치 수 1 Java: 재귀와 DP 실행 횟수 구하기

백준 단계별 풀기의 동적 계획법 1을 모두 풀어 둔 뒤 새 문제가 추가되어 다시 풀었다. 난이도는 브론즈 1이지만, 같은 피보나치 수를 구해도 재귀와 동적 계획법의 실행량이 얼마나 달라지는지 직접 드러내는 문제다.

문제에는 두 의사 코드가 주어진다. 하나는 정의 그대로 재귀 호출하고, 다른 하나는 작은 값부터 배열을 채운다. 요구하는 값은 피보나치 수 자체가 아니라 각 의사 코드에서 표시된 코드가 실행되는 횟수다.

첫 번째 횟수는 왜 F(n)일까

재귀 의사 코드에서 세려는 코드는 n = 1 또는 n = 2인 기저 조건에서 한 번 실행된다. 그 실행 횟수를 C(n)이라고 하면 다음 관계가 생긴다.

C(1) = 1
C(2) = 1
C(n) = C(n - 1) + C(n - 2)

이 식은 피보나치 수의 정의와 같다. 따라서 첫 번째 출력은 F(n)이다. 실제 재귀 함수를 끝까지 실행해 횟수를 세지 않아도, 피보나치 수만 구하면 된다.

예를 들어 n = 5라면 기저 조건의 코드는 5번 실행된다.

F(1), F(2), F(3), F(4), F(5)
  1     1     2     3     5

두 번째 횟수는 왜 n-2일까

동적 계획법 의사 코드는 반복문에서 i = 3부터 i = n까지 값을 한 번씩 저장한다. 세려는 코드가 반복마다 정확히 한 번 실행되므로 실행 횟수는 다음과 같다.

n - 3 + 1 = n - 2

n = 5라면 i = 3, 4, 5에서 세 번 실행되어 정답은 5 3이다. n = 30의 정답은 832040 28이다.

재귀를 그대로 실행하지 않는 Java 풀이

입력 범위는 5 ≤ n ≤ 40이다. F(40) = 102334155이므로 int 범위 안에 들어온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int previous = 1;
        int current = 1;

        for (int i = 3; i <= n; i++) {
            int next = previous + current;
            previous = current;
            current = next;
        }

        System.out.println(current + " " + (n - 2));
    }
}

주어진 재귀를 그대로 실행하면 같은 부분 문제를 여러 번 다시 계산한다. 호출 횟수는 피보나치 수에 비례해 지수적으로 늘고, 호출 스택은 깊이 O(n)을 사용한다. 위 풀이는 필요한 피보나치 수를 한 번만 누적하므로 시간 복잡도 O(n), 추가 공간 O(1)이다.

이 문제의 학습 포인트는 “재귀가 무조건 나쁘다”가 아니다. 중복되는 부분 문제가 있는 재귀를 그대로 실행하지 않고, 실행 횟수의 규칙을 식으로 바꾸는 것이다. 일반적인 DP 점화식의 상태 구성이 궁금하다면 백준 2156 포도주 시식을, 큰 피보나치 수를 빠르게 구하는 방식은 백준 11444 피보나치 수 6에서 이어서 볼 수 있다.

참고 자료

• 백준 24416 알고리즘 수업 - 피보나치 수 1