[BOJ] 1003번 피보나치 함수

굉장히 당황했던 문제였다.

https://www.acmicpc.net/problem/1003

재귀함수를 통해 피보나치함수를 구하는 예제코드가 나와있었고, 아주 간단하게 보여서

단순히 fibonacci(0)일 때와 fibonacci(1)일 때의  chknum을 증가시켜 문제를 풀고자 했다.

처음 내가 시도했던 코드는 아래와 같다.

#include <cstdio>
using namespace std;
 
int chkzero=0;
int chkone=0;
 
int fibonacci(int n) {
    if (n == 0) {
        chkzero++;
    } else if (n == 1) {
        chkone++;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
 
int main() {
    int loop;
    scanf("%d", &loop);
    int testcase[loop];
    for(int i=0; i<loop; i++)
        scanf("%d", &testcase[i]);
 
 
    for(int i=0; i<loop; i++) {
        fibonacci(testcase[i]);
        printf("%d %d\n", chkzero, chkone);
        chkzero=0;
        chkone=0;
    }
    return 0;
}

단순히 1003번이라 간단한가보다 라고 제출하고 나는 당황했다.

시간초과가 떴기 때문이다!

그리고 문제의 제약조건을 다시 보았다.

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.25 초 (언어별 추가 시간 없음)	128 MB	46974	9003	7108	30.823%

아... 시간제한이 0.25초이다.

그래서 시간을 줄이기 위해 동적계획법을 사용하였다.

피보나치수열은 D[n] = D[n-1] + D[n-2];로 나타낼 수 있고,

0이 호출되는 개수는 D[0]일때 1번, D[1]일 때 0번이고 그 후엔 D[n] = D[n-1] + D[n-2]로 셀 수 있었다.

따라서 dp0배열을 {1, 0, }으로 초기화해뒀다.

똑같이 1이 호출되는 개수는 D[0]일 때 0번, D[1]일 때 1번이며 그 후엔 D[n] = D[n-1] + D[n-2]로 셀 수 있었다.

따라서 dp1배열을  {0, 1, 0, }으로 초기화해뒀다.

( {0, 1, }로 초기화 하지 않은 이유는 dp1[2]부터 dp[41]까지의 모든 값을 0으로 초기화하기 위함.)

#include <cstdio>
using namespace std;
 
 
void fibonacci(int n) {
    int dp0[41]={1,0,},dp1[41]={0,1,0,};
    for(int i=2; i<=n; i++) {
        dp0[i] = dp0[i-2] + dp0[i-1];
        dp1[i] = dp1[i-2] + dp1[i-1];
    }
    printf("%d %d\n",dp0[n], dp1[n]);
}
 
int main() {
    int loop;
    scanf("%d", &loop);
    int testcase[loop];
    for(int i=0; i<loop; i++)
        scanf("%d", &testcase[i]);
 
    for(int i=0; i<loop; i++)
        fibonacci(testcase[i]);
    return 0;
}

그리고 결국 나는 맞았습니다. 라는 문구를 볼 수 있었다^.^

9502181	kim@@@@@	1003	맞았습니다!!	1116 KB	0 ms	C++14 / 수정	503 B	2분 전
9501784	kim@@@@@	1003	시간 초과			C++14 / 수정	591 B	26분 전