2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된
www.acmicpc.net
피보나치 수는 너무나 유명하기때문에
점화식을 알면 쉽게 계산을 할 수 있다.
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import java.util.*;
class Main {
public static int fibo(int n) {
if(n < 2) return n;
return fibo(n-1) + fibo(n-2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(fibo(n));
}
}
|
cs |
수식그대로 풀이를 하면 다음과 같이 함수를 만들 수 있다.
하지만 해당 수식으로 제출하면
시간 초과가 발생한다.
사실, 재귀적으로 풀면 모든 문제가 해결될 것 같지만
내부적으로 계속 값을 계산하기때문에 효율성을 고려해야한다.
배열로 답을 계산한 값을 넣어두고 n이 들어왔을때 배열에 값이
있으면 가져오는식으로 변경하면 좀더 효율적으로 풀 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.*;
class Main {
private static int[] cache = new int[1000];
public static int fibo(int n){
int result = 0;
if (cache[n] != 0) return cache[n];
if (n < 2) {
return n;
} else {
result = fibo(n-1) + fibo(n-2);
cache[n] = result;
return result;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(fibo(n));
}
}
|
cs |
