[java] 백준 2747번 피보나치 수

문제를 설명하기 앞서 이 아래의 문제와 같은 문제이다. 예제 입력과 출력은 같다.

[java] 백준 10870번 피보나치 수 5

이 문제와 위의 문제의 차이점은 n의 범위다. 10870번 문제에서 n은 20이었고, 이번 2747번 문제에서는 n은 45이다.

또한 티어의 차이도 있는데 약간 애매하다...

 

10870 티어가 좀 더 높은데 난 뒤바꼈다고 생각한다.

10870문제에서 쓰던 소스를 복붙했더니 시간 초과가 나버렸다. 

 

그래서 생각한 방법은

n은 0~45까지의 범위이기 때문에 배열을 46개 정도 만들고 미리 45번째까지 값을 만들어 놓은 다음 해당 배열의 값을 뽑아내는 것이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println(recur(n));
    }

    public static int recur(int n){
        int[] arr = new int[46];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;

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

        return arr[n];
    }
}

역시나 성공...