문제

BOJ 1003, 피보나치 함수

핵심

• 피보나치수열로 n == 0일 때 0을 호출하고 n == 1일 때, 1을 호출한다면 fibonacci(n)을 호출했을 때 0과 1의 호출된 횟수를 각각 구해야 한다.
• fibo(n) 함수를 한 번 호출하면 내부에서 fibo(n - 2), fibonacci(n - 1) 2번 호출된다. 즉 대략적인 시간복잡도는 $2^n$으로 n이 40일 땐 상당히 큰 숫자로 조 단위가 넘어간다. 즉 단순하게 0을 호출할 때 0의 개수를 증가시키고, 1을 호출할 때 1의 개수를 증가시키면 시간 초과가 된다.
• dynamic programming으로 O(n)에 해결할 수 있다. 부분 문제를 해결하기 위해 테이블을 작성한다.
  • dp[i][k]: i번째 피보나치 수를 호출했을 때 k가 호출되는 횟수. k는 0 또는 1
  • 피보나치수열은 0, 1, 1, 2, 3, 5 ... 초기식은 dp[0] = 0, dp[1] = 1로 정의한다.
    - fibo(2)는 fibo(1)과 fibo(0)을 호출하므로 1과 0이 하나씩 있, fibo(3)은 fibo(2)와 fibo(1)을 호출하므로 fibo(2)의 0과 1의 개수와 fibo(1)의 0과 1의 개수를 더한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

int dp[44][2];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	dp[0][0] = 1;
	dp[1][1] = 1;
	for (int i = 2; i <= 40; ++i) {
		dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
		dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
	}
	while (t--) {
		int n; 
		cin >> n;
		cout << dp[n][0] << ' '<< dp[n][1] << '\n';
	}
}

Java

import java.io.*;

public class Main {
    static int[][] dp = new int[44][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        dp[0][0] = 1;
        dp[1][1] = 1;
        for (int i = 2; i <= 40; i++) {
            dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
            dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
        }
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][0] + " " + dp[n][1] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}