[백준 1003번 피보나치 함수]

피보나치 수열을 푸는 방법 중 가장 잘 알려진 방법은 재귀함수를 쓰는 방법이다.

public int fibonacci(int num) {
        if(num <= 1) {
            return num;
        }
        else {
            return fibonacci(num-1) + fibonacci(num-2);
        }
    }

하지만 위와같은 방식은 매우 비효율적이다. 당장 fibonacci(5)만 봐도

중복 연산이 상당히 많다는 사실을 알 수 있다.

위의 단점을 없에려면 중복 연산되는 값들을 어딘가에 저장해 놓아야 할 것이다.

동적 계획법

public int fibonacci(int input) {
        int[] ans = new int[input+1];
        
        if(input <= 1) {
        	return input;
        } else {
        	ans[0] = 1; ans[1] = 0;
        	for(int i = 2; i<=input; i++) {
            	ans[i] = ans[i-1]+ ans[i-2];
        	}
        	return ans[input];
        }
        
    }

작은 숫자부터 차근차근 올라가서 최종 문제를 푸는 방식이다.

먼저 ans[0] = 0; ans[1] = 1;로 초기값을 정한 다음

for문으로 작은 숫자부터 ans[i-1] + ans[i-2]를 구해서 배열 ans[i] 에 저장해놓는다.

그렇게 쭉 더해가다가 최종 값 ans[n] 까지 구한다.

f(0) 과 f(1)의 개수를 구하는 방법도 위를 응용해서 풀면 된다.

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

public class Main1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testcase = Integer.parseInt(br.readLine());
        int[] arr = new int[testcase];

        for(int i = 0; i< testcase; i++) {
            int k = Integer.parseInt(br.readLine());
            arr[i] = k;
        }
        for (int i : arr) {
            if(i == 0) System.out.println(1+" "+0);
            else if(i == 1) System.out.println(0+" "+1);
            else {
                int[][] result = fibonacci(i);
                System.out.println(result[i][0] + " " + result[i][1]);
            }
        }
    }
    public static int[][] fibonacci(int input) {
        int[][] ans = new int[input+1][2];
        ans[0][0] = 1; ans[0][1] = 0;
        ans[1][0] = 0; ans[1][1] = 1;
        for(int i = 2; i<=input; i++) {

            ans[i][0] = ans[i-1][0] + ans[i-2][0];
            ans[i][1] = ans[i-1][1] + ans[i-2][1];
        }
        return ans;
    }
}