[백준(BOJ)] 1003번 : 피보나치 함수 - C++[CPP]

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

---

 

 

 

⊙ 문제

 

 

⊙ 입력

 

 

⊙ 출력

 

 

⊙ 예제 입출력

 

 

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

제한시간 때문에 상당히 애쓴 문제다.

정상적으로 출력되는데 시간 초과가 떠서 cin, cout을 printf와 scanf로 바꿨다. 그래도 시간 초과가 떴다.

 

내 첫 번째 풀이다. (시간 초과)

#include <iostream>

using namespace std;

int count_zero = 0;
int count_one = 0;

int fibonacci(int n) {
    if (n == 0) {
        count_zero++;
        return 0;
    } else if (n == 1) {
        count_one++;
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main() {
    int T;
    cin >> T;
    int n[T];
    
    for (int i = 0; i < T; i++) {
        cin >> n[i];
    }
    
    for (int i = 0; i< T; i++) {
        fibonacci(n[i]);

        cout << count_zero << " " <<count_one << '\n';

        count_zero =0;
        count_one =0;
    }
}

문제에서 주어진 재귀 함수 fibonacci를 살짝 변형해 0과 1에서 count 값을 셌다.

결과는 시간 초과

 

0.25초라는 시간제한이 있기 때문에 시간 초과가 나올 수밖에 없는 코드다.

왜냐하면 반복문 안에, 재귀 함수인 fibonacci가 있기 때문이다.

※피보나치의 시간복잡도만해도 O(2^n)이다.

 

 

시간 복잡도를 더 줄여야 한다.

 

아무리 생각해도 내가 접근한 알고리즘에서 더 이상의 최적화는 생각나지 않았다.

count로 풀기 위해선 재귀 함수를 계속 호출한다. 계속 호출하면 소요 시간은 필연적으로 계속 늘어난다.

N값이 40으로 제한되어 있어도 재귀 함수 피보나치를 사용하면 0.25초 안에 해결하지 못할 거라는 판단이 섰다.

 

한참을 생각했다. 그러다 문뜩 떠올랐다.

 

피보나치의 점화식을 이용하여 0과 1의 count를 구하는 것이 아닌

0과 1의 count 점화식을 구하면 되지 않을까라는 생각이.

 

( T = 0 ) -> 0은 1, 1은 0

( T = 1 ) -> 0은 0, 1은 1

( T = 2 ) -> 0은 1, 1은 1

( T = 3 ) -> 0은 1, 1은 2

( T = 4 ) -> 0은 2, 1은 3

( T = 5 ) -> 0은 3, 1은 5

( T = 6 ) -> 0은 5, 1은 8

 

• 0과 1의 count 점화식 (j>=2)

            zero[j] = zero[j-1] +zero[j-2];

            one[j] = one[j-1] + one[j-2];

 

---

 

⊙ 문제 풀이

#include <iostream>

int main() {
    int zero[41]={1,0,};
    int one[41]={0,1,};
    int T,n;

    scanf("%d",&T);
    for (int i=0; i<T; i++) {
        scanf("%d",&n);
        for (int j = 2 ; j<=n; j++) {
            zero[j] = zero[j-1] +zero[j-2];
            one[j] = one[j-1] + one[j-2];
        }
        printf("%d %d\n",zero[n],one[n]);
    }

}

---

⊙ 결과

 

 

 

---

 

 

⊙ 마무리

 

 

코딩도 수학을 해야 한다..

 

좋아요는 로그인하지 않아도 누를 수 있습니다!