[c++ | 백준] 1003번 피보나치 함수

c++ 문제 풀이

 

 

 

 

 

 

---

 

 

[백준 1003번 피보나치 함수 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
using namespace std;

int fibo[41] = { 0, 1, 1 };

int fibonacci(int n) 
{
    if (n <= 2 || fibo[n] != 0) return fibo[n];
    fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fibo[n];
}

int main(void)
{
    int t, n;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        if (n == 0)
        {
            cout << "1 0\n";
            continue;
        }
        cout << fibonacci(n - 1) << ' ' << fibonacci(n) << "\n";
    }

    return 0;
}

 

 

 

풀이 설명

 

1. 일반적인 피보나치 함수로는 풀리지 않는다?

 

분명 나는 정석대로 풀었는데, 시간 초과를 보시고 블로그를 찾아오신 분들이 많으실 거라고 생각됩니다.

이 문제는 숨겨져있는 규칙과 다이나믹프로그래밍을 적용해야만 풀리는 문제입니다.

 

먼저 다이나믹프로그래밍에 대해서 알고싶으시다면 밑에서 확인해주세요!

https://ayun-programmer.tistory.com/35

[c++] 알고리즘 설계 기법 | DP(다이나믹 프로그래밍)

 

 

2. 숨겨진 규칙

n에 대해서 fibonacci(n)을 실행시켰을 때, fibonacci(0)과 fibonacci(1)이 몇 번 실행되는지 알아야하는데요.

이 결과 값을 나란히 놔둬보면 규칙이 보입니다.

 

N	zero	one
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13

 

one 열을 보시면 값이 피보나치 수열과 똑같습니다. 즉 fibonacci(n)의 값과 같다는 걸 알 수 있습니다.

다음으로 zero 열을 보시면 정확하게 n이 0일 때를 제외하고 one 열의 n - 1값을 가지는걸 볼 수 있습니다. 즉 fibonacci(n - 1)의 값과 같다는 걸 알 수 있습니다.

 

따라서 우리가 출력해야 될 값은 fibonacci(n)값(1에 해당)과 fibonacci(n - 1)값(0에 해당)이 되는 것 입니다.

 

cin >> n;
if (n == 0)
{
    cout << "1 0\n";
    continue;
}
cout << fibonacci(n - 1) << ' ' << fibonacci(n) << "\n";

이렇게 n이 0인 예외 처리를 제외하고 저렇게 출력해주면 문제가 해결됩니다.

 

---

 

이렇게 백준 1003번 문제를 규칙과 다이나믹프로그래밍으로 풀이해보았습니다.

궁금한점 있으시면 댓글 남겨주세요!