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

풀이

이 문제는 dp를 이용한 피보나치 수열문제의 연장선이다. 문제에서는 0과 1이 출력하는 수 구하라고 하였는데 이는 곧 dp로 치환하여 풀면 다음과 같다.

f_0(n) --> n일때 0의 출력수

f_1(n) --> n일때 1의 출력수

라고 가정을 한다면 이는 f_0(2) = f_0(1) +f_0(0), f_0(3) = f_0(2) + f_0(1) 과 같다. 그러므로 기존에 하던 dp그대로 하면된다. 하지만 여기서 주의해야할 점은 0과1 을 동시에 처리해줘야하는것이다. (아니면 시간초과가 난다... 자바....ㅜㅜ)

 

코드

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

class Main {

    static Integer[][] count = new Integer[41][2];
    static int now = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

//        Arrays.fill(count_0, -1);
//        Arrays.fill(count_1, -1);


        count[0][0] = 1;
        count[0][1] = 0;

        count[1][0] = 0;
        count[1][1] = 1;

        for (int t = 0; t < T; t++) {
            int temp = Integer.parseInt(br.readLine());
            fibonacci(temp);
            System.out.println(count[temp][0] + " " + count[temp][1]);
        }

    }


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

        return count[n];
    }
}