BOJ 24416 - 알고리즘 수업 - 피보나치 수 1

문제

BOJ 24416 - 알고리즘 수업 - 피보나치 수 1

피보나치 수를 재귀(naive)로 계산할 때와 동적 프로그래밍(DP)으로 계산할 때의 if (n < 2) return n 코드 실행 횟수를 각각 구하는 문제다. 재귀 방식은 지수적으로 호출이 늘어나는 반면, DP 방식에서 해당 줄은 정확히 1번 실행된다(초기화 단계 제외). 재귀 호출 횟수를 직접 세는 대신, DP로 피보나치를 계산하면서 재귀 기저 조건 실행 횟수를 수식으로 도출할 수 있다.

입력

• 첫째 줄: 자연수 n (5 이상 40 이하)

출력

재귀 알고리즘의 코드1 실행 횟수와 DP 알고리즘의 코드2 실행 횟수를 공백으로 구분하여 출력한다.

예제

풀이

재귀 피보나치의 기저 조건 호출 횟수는 fib(n)과 동일하고, DP 방식에서 n-2번 루프를 돌면서 각 d[i]를 채우므로 실행 횟수는 n-2이다.

1. DP 테이블 d[0..40]을 미리 초기화 (d[1]=1, d[2]=1부터 점화식 적용)
2. d[N] = 재귀 방식의 코드1 실행 횟수 (피보나치 수 자체)
3. N - 2 = DP 방식의 코드2 실행 횟수

핵심 아이디어: 재귀 피보나치에서 if (n < 2) return n이 실행되는 횟수는 fib(n)과 동일하다는 수학적 사실을 이용하면, 별도의 재귀 호출 없이 DP 테이블 값만으로 두 횟수를 모두 구할 수 있다.

코드

package com.ssafy.an.day149;
 
import java.util.Scanner;
 
public class Day118BOJ24416피보나치 {
	static int N;
	static int[] d;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
 
		d = new int[41];
		d[0] = 0;
		d[1] = 1;
		d[2] = 1;
		d[3] = 2;
		for (int i = 3; i < 41; i++) {
			d[i] = d[i - 2] + d[i - 1];
		}
		System.out.println(d[N] + " " + (N - 2));
		sc.close();
	}
}

복잡도

• 시간: O(N) — DP 테이블을 한 번 순회
• 공간: O(N) — DP 배열 크기 41