1003번 피보나치 함수 문제를 풀어보고있다.(1)
1003 피보나치 함수
https://www.acmicpc.net/problem/1003
피보나치 수열은 n번째 피보나치 수열은 n-1번째 수열과 n-2번째 수열을 더한 결과값이다.
이번에 풀고있는 문제는 n번째 피보나치 수열에서 호출되는 0과 1이 몇 번 계산되는지 출력하는 문제이다.
비교적 간단한 문제로 보이지만 예전에 이 문제를 풀 때, 시간제한 때문에 꽤나 애를 먹고 포기했던 문제이다.
#include <stdio.h>
int c0=0,c1=0;
int fibonacci(int n) {
if (!n) {
c0++;
return 0;
}
else if (n==1) {
c1++;
return 1;
}
else return fibonacci(n-1)+fibonacci(n-2);
}
int main()
{
int t,a,i;
scanf("%d", &t);
for(i=0; i<t; i++) {
scanf("%d", &a);
fibonacci(a);
printf("%d %d\n", c0, c1);
c0=0;
c1=0;
}
return 0;
}
이것이 내가 예전에 처음 만든 코드였다.
입력 범위는 0<=N<=40이다.
보기만해도 재귀함수로 호출될 때마다 연산을 하기때문에 입력값이 15만 넘어가도 1초를 가볍게 넘어갈 것이다.
이 문제의 시간제한은 0.25초, 따라서 그에 맞는 점화식을 세워야 했다.
그래서 fibonacci(n)에서 fibonacci(0)과 fibonacci(1)이 사용되는 횟수를 생각해보았다.
n |
0 |
1 |
2 |
3 |
4 |
5 |
fibonacci(0) |
1 |
0 |
1 |
1 |
2 |
3 |
fibonacci(1) |
0 |
1 |
1 |
2 |
3 |
5 |
이렇게 써놓고 보니 D[n]=D[n-1]+D[n-2]라는 규칙을 알 수 있었다.
#include <stdio.h>
#include <stdlib.h>
int check[40]={1,1};
int fibonacci(int n) {
if (n<=1) return check[n];
else if (check[n]>0) return check[n];
return check[n]=fibonacci(n-1)+fibonacci(n-2);
}
int main()
{
int t,a,i;
scanf("%d", &t);
for(i=0; i<t; i++) {
scanf("%d", &a);
if(a==0) printf("1 0\n");
else if(a==1) printf("0 1\n");
else {
fibonacci(a);
printf("%d %d\n", check[a-2], check[a-1]);
}
}
return 0;
}
이것이 내가 다시 만든 코드이다.
시간초과는 해결했지만 근본적으로 틀렸다는 결과가 나왔다.
오늘은 이 문제를 해결해보려고 한다.