` 다이나믹 프로그래밍
N=3 일때
$fibo(3) = fibo(2) + fibo(1) = (fibo(1) + fibo(0)) + fibo(1)$ 이라 할 수 있다.
또한 계속 구해보면
- fibo(0)은 1,0,1,1,2,3,5….
- fibo(1)은 0,1,1,2,3,5….
으로 피보나치 함수 형태를 띄는 것을 알 수 있다.
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class B1003 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
List<Integer> zero = new ArrayList<>();
List<Integer> one = new ArrayList<>();
for(int i=0;i<2;i++) {
zero.add(1-i);
one.add(i);
}
int T = Integer.parseInt(br.readLine());
int max =1;
for(int i=0;i<T;i++) {
int N = Integer.parseInt(br.readLine());
if(max < N) {
for(int k=max+1;k<=N;k++) {
zero.add(zero.get(k-1) + zero.get(k-2));
one.add(one.get(k-1) + one.get(k-2));
}
max = N;
}
sb.append(zero.get(N)).append(" ").append(one.get(N)).append("\n");
}
System.out.println(sb);
}
}
|