[백준] 2748 : 피보나치 수 2(JAVA)

피보나치 수 2

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

79859

32236

26459

40.028%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

---

DP 방식 - 메모이제이션

이미 계산했던 전력이 있는 놈을 다시 계산해주지 않는 것 →그러기 위해서는 배열을 사용한다.;

배열의 인덱스를 key 배열의 값을 value로 사용해

중복되는 계산을 없애주었습니다.

package Day1114;

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

public class B2748 {
	static long[] arr = new long[91];

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

	}

	static long fibo(int n) {

		if (n <= 1)
			return n;
	
		if (arr[n] != 0)
			return arr[n];

		arr[n] = fibo(n - 1) + fibo(n - 2);
		return arr[n];
	}
}

---

시간 초과

package Day1114;

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

public class B2748 {

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

	}

	static int fibo(int n) {

		if (n == 0)
			return 0;
		if (n == 1)
			return 1;

		return fibo(n - 1) + fibo(n - 2);

	}

}

n이 20정도면 몰라서 해당 문제는 90까지 허용하고 있다.

그렇기 때문에 아무리 BufferedReader로 해도 시간이 초과되는 것 같다.

나올 수 있는 최대값이 long형의 최대값보다 크기때문에 애초에 틀린 코드이다.