Problem Solving/Java
백준 2748번 피보나치 수열 동적계획법 활용 2가지 풀이 ( Java )
TakeKnowledge
2019. 10. 24. 05:47
반응형
2748번: 피보나치 수 2
문제 피보나치 수는 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번째 피보나치 수를
www.acmicpc.net
- Top-Down ( 재귀 함수 호출 ) 방식
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public class Main {
static long[] memo;
// 메모이제이션 배열 생성
static long fibonacci(int n) {
if(n<=1) {
// 0과 1은 답을 구할 수 없는 가장 작은 수
return n;
}else {
if(memo[n]>0) {
// 메모 되어 있다면
return memo[n];
// 메모 값을 리턴
}
memo[n] = fibonacci(n-1) + fibonacci(n-2);
// 재귀 호출 보내서 받은 값을 메모에 담고
return memo[n];
// 메모를 리턴
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// reader writer 생성
memo = new long[91];
int n = Integer.parseInt(br.readLine());
long answer = fibonacci(n);
}
}
|
- Bottom-Up ( 반복문 활용 ) 방식
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public class FibonacciNumber2BottomUp {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// reader writer 생성
int n = Integer.parseInt(br.readLine());
long[] fibonacci = new long[91];
fibonacci[0] = 0;
fibonacci[1] = 1;
for (int i = 2; i <= n; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
}
}
|
반응형