[Java][백준] #1003 - 피보나치 함수

🔗 백준 1003 - 피보나치 함수

문제

알고리즘 분류

• 다이나믹 프로그래밍

---

풀이

1. 호출 값을 저장할 배열

• 이 문제에서는 0이라는 값도 의미를 가지므로 int가 아닌 Integer로 구현해 null체크

    static Integer f[][] = new Integer[41][2];
	...
        f[0][0] = 1; //fibo(0)이 호출될 때 0이 출력되는 횟수
        f[0][1] = 0; //fibo(0)이 호출될 때 1이 출력되는 횟수
        f[1][0] = 0; //fibo(1)이 호출될 때 0이 출력되는 횟수
        f[1][1] = 1; //fibo(1)이 호출될 때 1이 출력되는 횟수

2. fibo() 함수 구현

    public static Integer[] fibo(int n){
        if(f[n][0] == null || f[n][1] == null){
            f[n][0] = fibo(n-1)[0] + fibo(n-2)[0];
            f[n][1] = fibo(n-1)[1] + fibo(n-2)[1];
        }
        return f[n];
    }

3. f[n]의 0, 1 출력 횟수 구하기

• test case 수 만큼 반복

        for(int i = 0; i< t; i++){
            int n = Integer.parseInt(br.readLine());
            f[n] = fibo(n);
            System.out.println(f[n][0] + " " + f[n][1]);
        }

전체 코드

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

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

        f[0][0] = 1;
        f[0][1] = 0;
        f[1][0] = 0;
        f[1][1] = 1;

        for(int i = 0; i< t; i++){
            int n = Integer.parseInt(br.readLine());
            f[n] = fibo(n);
            System.out.println(f[n][0] + " " + f[n][1]);
        }
    }
    public static Integer[] fibo(int n){
        if(f[n][0] == null || f[n][1] == null){
            f[n][0] = fibo(n-1)[0] + fibo(n-2)[0];
            f[n][1] = fibo(n-1)[1] + fibo(n-2)[1];
        }
        return f[n];
    }
}