[백준 알고리즘 C/C++] 1003번 문제 풀이 : 피보나치 함수

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 실버 3

백준 알고리즘 1003번 문제 피보나치 함수

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

1003번: 피보나치 함수

 

---

● 풀이 방법

문제에서 제공된 피보나치 수를 구하는 C++ 함수를 그대로 사용해서 값을 산출해 내는 소스를 적어도 동작상에서는 문제가 되지 않는다. 대신 문제의 시간제한이 0.25초 이기에 의도한 정답은 아니다.

 

아래와 같이 시간초과가 뜬다.. 재귀함수로 인해 시간초과가 뜨는 것. 우리는 이 문제를 해결해야 한다.

 

피보나치 함수에 대입이 될 N의 제한 조건이 있다. 

우리는 총 40까지의 피보나치 함수 값을 구하면 되는 것.

피보나치 함수에 값을 대입하여 결과 값을 보면 규칙이 존재한다.

 

fibonacci(5)를 기준으로 보자.

1과 0의 값은 결국

fibonacci(3)과 fibonacci(4)의 결과 값의 합이다.

즉 구하고자 하는 피보나치의 값이 N-2 값과 N-1의 값 합이라는 뜻이다.

이 점을 이용해 결과값을 재귀함수를 사용하지 않고 빠르고 쉽게 구할 수 있다.

---

● 소스 코드

** 아래의 소스는 피보나치의 값의 규칙을 알아내어 미리 2중 배열안에 저장한 후, 사용자가 원하는 fibonacci(N)의 값을 즉각적으로 출력해주는 구조입니다. 

** 바람직한 소스는 아니라고 판단이 되며 더 나은 소스가 존재할 가능성이 높습니다.

#include <iostream>

int main(void)
{
    int test_case = 0;
    int ret[41][2];
    int N = 0;
    
    //피보나치 함수에서 0의 값 대입
    ret[0][0] = 1;
    ret[0][1] = 0;

    //피보나치 함수에서 1의 값 대입
    ret[1][0] = 0;
    ret[1][1] = 1;
    
    std::cin >> test_case; 

    //피보나치 함수 2 ~ 40 까지의 값
    for(int i=2;i<41;i++){
        ret[i][0] = ret[i-2][0] + ret[i-1][0];
        ret[i][1] = ret[i-2][1] + ret[i-1][1];
    }

    for(int i = 0; i < test_case; i++){
        std::cin >> N;
        std::cout << ret[N][0] << " " << ret[N][1] << std::endl;
    }
    return 0;
}

 

피보나치 함수 N의 결과 값은

N-2와 N-1의 값 합이라고 했으니, fibonacci(0)과 fibonacci(1)의 값은 미리 알고 있어야 한다.

그렇기에 미리 두 값을 ret 이중배열안에 넣어 둔 후 40까지의 값을 계산하여 저장해 두는 방식을 사용했다.

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무