문제 분석
작성코드
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
42
43
44
45
46
47
48
49
50
51
52
| import java.io.*;
class Main {
static int[] D;
static int cnt_dp;
static int cnt_recursion;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
// 일반 재귀함수를 통한 코드1 실행 횟수 카운트
cnt_recursion = 0;
fibo_recursion(N);
// DP 테이블 초기화, 0번째는 0, 첫번째는 1
D = new int[N+1];
for(int i=0; i<=N; i++) {
D[i] = -1;
}
D[0] = 0;
D[1] = 1;
// DP 재귀 호출하여 코드2 실행횟수 카운트
cnt_dp = 0;
fibo_dp(N-1);
bw.write(cnt_recursion + " " + cnt_dp+"\n");
bw.close();
br.close();
}
static int fibo_recursion(int n) {
if(n == 1 || n == 2) {
cnt_recursion++;
return 1;
}else {
return fibo_recursion(n-1) + fibo_recursion(n-2);
}
}
static int fibo_dp(int n) {
if(D[n] != -1) {
return D[n];
} else {
cnt_dp++;
return D[n] = fibo_dp(n-1) + fibo_dp(n-2);
}
}
}
|
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.
