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

풀이 과정

처음에는 재귀함수로 해결하려고 했으나 점점 복잡해지는 것 같아서 풀이 방향을 바꿨다. 이런 문제를 해결할 때 점화식이 중요하다. 반복되는 부분을 찾아야한다.
아래 부분에서 볼 수 있듯이 n에 대한 0의 호출은 n-1의 1 호출과 동일하고 n에 대한 1의 호출은 n-1의 0 호출과 1 호출의 합과 동일하다는 점을 이용해서 해결했다.

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

public class Main {
    static int zero[] = new int[41];
    static int one[] = new int[41];
    static StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        zero[0] = 1;
        zero[1] = 0;
        one[0] = 0;
        one[1] = 1;

        for (int i = 2; i < 41 ; i++) {
            zero[i] = one[i-1];
            one[i] = zero[i-1] + one[i-1];
        }

        for (int j = 0; j < n; j++) {
            System.out.println(zero[input[j]] + " " + one[input[j]]);
        }

    }
}