반응형
문제 출처
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
문제 이해하기
재귀함수와 피보나치 수열을 이해하며 0과 1이 몇번 출력되는지 횟수를 구하면된다.
|
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
|
#include <stdio.h>
#include <stdlib.h>
int zero,one;
int fibonacci(int n) {
if(n==0) {
zero++;
return 0;
} else if (n == 1) {
one++;
return 1;
} else
return fibonacci(n-1) + fibonacci(n-2);
}
int main(int argc, char *argv[]) {
int cnt, n;
scanf("%d",&cnt);
for(; cnt>0; cnt--) {
zero = 0;
one = 0;
scanf("%d",&n);
fibonacci(n);
printf("%d %d\n",zero,one);
}
return 0;
}
|
실제 문제의 핵심내용이 다있지만 문제는 실행 시간이였다.
재귀함수 특성상 값이 크면 함수도 그만큼 많이 불러와야 하기 때문에 실행시간도 길어지는 건 당연한 결과였다.
해결 방법은 계산된 값을 또 계산하지 않게 해주면 되는것이다.
|
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
|
#include <stdio.h>
#include <stdlib.h>
int fibo [41]= {1,1,};
int fibonacci(int n) {
if(n<=1)
return 1;
else if(fibo[n]>0)
return fibo[n];
return fibo[n] = fibonacci(n-1) + fibonacci(n-2);
}
int main(int argc, char *argv[]) {
int cnt, n;
scanf("%d",&cnt);
for(; cnt>0; cnt--) {
scanf("%d",&n);
if(n ==0)
printf("1 0\n");
else if(n==1)
printf("0 1\n");
else {
fibonacci(n);
printf("%d %d\n",fibo[n-2],fibo[n-1]);
}
}
return 0;
}
|
반응형
'Computer Language > Algorism' 카테고리의 다른 글
| [백준알고리즘] 11720 숫자의 합 (0) | 2019.05.05 |
|---|---|
| [백준알고리즘] 별찍기 2438, 2439, 2440, 2441 (0) | 2019.05.04 |
| [백준알고리즘] 2839 설탕배달 (0) | 2019.05.03 |
| [백준알고리즘] 1단계 입/출력을 받아보기 (0) | 2019.05.02 |
| [백준 알고리즘] 1002번 터렛 (0) | 2019.04.30 |