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

https://www.acmicpc.net/problem/1003

각 테스트 케이스마다 0과 1이 출력되는 횟수를 구하는 문제이다.

코드

public class Main {

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

        for (int i = 0; i < tc; i++) {
            int N = Integer.parseInt(br.readLine());
            int[][] fibonacci = new int[41][2];
            //초기값
            fibonacci[0][0] = 1;
            fibonacci[0][1] = 0;
            fibonacci[1][0] = 0;
            fibonacci[1][1] = 1;

            if (N < 2) {
                System.out.println(fibonacci[N][0] + " " + fibonacci[N][1]);
                continue;
            }
            //bottom-up
            for (int j = 2; j <= N; j++) {
                fibonacci[j][0] = fibonacci[j - 2][0] + fibonacci[j - 1][0];
                fibonacci[j][1] = fibonacci[j - 2][1] + fibonacci[j - 1][1];
            }
            System.out.println(fibonacci[N][0] + " " + fibonacci[N][1]);
        }
    }
}

 

n=8일 때 필요한 피보나치 수를 트리형태로 먼저 그려봤고 n이 1씩 증가할 때마다 0과 1의 출력횟수가 기하급수적으로 늘어나는 것을 확인할 수 있었다.

따라서 0.25초 안에 풀기 위해 0과 1의 출력 횟수 역시 DP로 풀어야 한다는 것을 알았고, n=0, n=1일 때 0과 1이 출력되는 횟수를 계산한 뒤 n을 1씩 늘려보았다.

그 결과, 피보나치 수와 마찬가지로 0과 1의 횟수도 규칙성 있게 증가하는 것을 발견했으며, Top-down방식 보단 Bottom-up방식이 더 적합하다고 판단, 위와 같이 문제를 풀었다.