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

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

1003번: 피보나치 함수

접근 방식

문제에서 C++ 코드를 제시한 것도 그렇고 정답 비율도 그렇고

전통적인 피보나치수열 구하는 코드로 풀기에는 의심스러운 것이 많은 문제였다.

시간 제한이 다른 문제들에 비해 많이 작은 것을 확인하고 다른 방식의 접근이 필요하다는 생각을 했다.

 

f(n) = (f(n-1)의 f(0)개수와 f(1)개수의 합) * f(1) + (f(n-1)의 f(1)의 개수) * f(0) 이라는 점화식을 도출했다.

 

시간과 메모리 제한을 고려해서 주어지는 값이 40으로 크지 않기 때문에

바텀업 방식으로 미리 계산을 해놓은 뒤에 값을 불러 출력하도록 구현했다.

 

2차원 배열을 만들어 n에 대한 0과 1의 개수를 담도록 구현했다.

 

 

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        int[] inputs = new int[T];

        for (int i = 0; i < inputs.length; i++) {
            inputs[i] = scanner.nextInt();
        }

        int[][] fibonacciSet = new int[41][2];

        fibonacciSet[0][0] = 1;
        fibonacciSet[0][1] = 0;
        fibonacciSet[1][0] = 0;
        fibonacciSet[1][1] = 1;

        for (int i = 2; i < fibonacciSet.length; i++) {
            fibonacciSet[i][0] = fibonacciSet[i - 1][1];
            fibonacciSet[i][1] = fibonacciSet[i - 1][0] + fibonacciSet[i - 1][1];
        }

        for (int input : inputs) {
            System.out.println(fibonacciSet[input][0] + " " + fibonacciSet[input][1]);
        }
    }
}