백준 1003 "피보나치 함수" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• fibonacci(n)을 호출할 때 0과 1이 몇 번 출력되는지 계산하는 문제.

fibonacci(3) 호출 시,
fibonacci(3) → fibonacci(2) + fibonacci(1)
fibonacci(2) → fibonacci(1) + fibonacci(0)

0은 1번, 1은 2번 호출됨.

---

🛠 풀이 및 알고리즘

1. dp[n][0]과 dp[n][1]을 사용하여 n일 때 0과 1의 호출 횟수를 저장
   • dp[n][0]: fibonacci(n)에서 0이 호출된 횟수.
   • dp[n][1]: fibonacci(n)에서 1이 호출된 횟수.
2. 재귀 + 메모이제이션(DP) 활용
   • 한 번 계산한 값은 저장하여 중복 연산 방지.
3. 반복문 방식으로 n ≤ 40까지 미리 계산하여,  최적화 가능

---

💡 코드

1. 재귀 + 메모이제이션(DP) 활용

public class Baekjoon_1003 {
    static int[][] dp = new int[41][2];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        // 1. DP 초기값 설정
        dp[0][0] = 1; // fibonacci(0)
        dp[1][1] = 1; // fibonacci(1)

        while (t-- > 0) {
            int n = sc.nextInt();

            // 재귀 + 메모이제이션(DP) 활용
            fibonacci(n);
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }

    static int[] fibonacci(int n) {
        if(dp[n][0] > 0 || dp[n][1] > 0){
            return dp[n];
        }
        dp[n][0] = fibonacci(n - 1)[0] + fibonacci(n - 2)[0];
        dp[n][1] = fibonacci(n - 1)[1] + fibonacci(n - 2)[1];

        return dp[n];
    }
}

 

2. 반복문으로 미리  n ≤ 40까지 미리 계산

public class Baekjoon_1003 {
    static int[][] dp = new int[41][2]; // 0과 1의 호출 횟수 저장

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        // 1. DP 초기값 설정
        dp[0][0] = 1;  // fibonacci(0)
        dp[1][1] = 1;  // fibonacci(1)

        // 2. 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];
        }

        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }
}

---

🏆 시간 복잡도 분석

• N번만큼 순회 : O(N)