<백준> 1003번 피보나치 함수 / C++ 풀이

중점

1. 시간 제한이 0.25초라는 것

2. 피보나치 수열을 사용하면서 0과 1이 출력되는 수를 구하는 것

 

설명:
재귀 함수를 이용하여서 피보나치 풀이를 하기에는 시간 제한이 있으므로 출제자가 원하는 풀이가 아니라고 할 수 있다. 따라서 DP알고리즘을 이용해서 풀이 해야한다는 생각을 할 수 있다. 이를 생각하게된 계기는 문제에서 피보나치 수열을 사용할 때 0과 1이 출력되는 수 count하는 것에서 아이디어를 얻었다. 이는 즉 초기값인 f(0)과 f(1)로 f(n)을 만드는 것과 같다. 예를 들면 f(2) = f(0) + f(1)이고 f(3) = f(2) + f(1)이다. 이를 다르게 표현하면 f(3) = 2f(1) + f(0)이라는 뜻이다. 따라서 각각의 n에 대해서 얼마의 0과 1로 이루어져 있는지를 파악하는 것이 요점이다. 행렬을 통해서 0과 1을 피보나치 수열을 이용해서 더하는 반복문을 선행적으로 수행한다. 이로 인해서 재귀함수를 사용하지 않으므로 시간적 이득을 볼 수 있다. 점화식을 이용한 바텀 업 DP 알고리즘을 사용해서 시간 제한에 알맞은 풀이를 진행한다.

 

---

 

정답 코드:

#include <bits/stdc++.h>

using namespace std;

int fibo[42][2];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    int n;

    cin >> t;

    fibo[0][0] = 1;
    fibo[1][1] = 1;

    for (int i = 2; i <= 40; i++){
        fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0];
        fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1];
    }

    while (t--)
    {
        cin >> n;

        cout << fibo[n][0] << ' ' << fibo[n][1] << '\n';
    }
}

 

⚙️DP 알고리즘 이란?

https://wnehgus101.tistory.com/entry/알고리즘-동적-계획법-DP-Dynamic-Programming

<알고리즘> 동적 계획법 (DP: Dynamic Programming)

 

감사합니다. 질문은 댓글로 부탁드립니다.