[BOJ/C++] 24417번 알고리즘 수업 - 피보나치 수 2

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

문제해석

 

피보나치 수를 구할 수 N을 입력한다.

문제에 나와있는 코드1, 코드2의 실행 횟수를 출력한다.

---

코드

 

#include <bits/stdc++.h>
using namespace std;

int fib(int n, deque<int> fibodeque)
{
    fibodeque.push_back(1);
    fibodeque.push_back(1);

    for (int i = 2; i < n; i++)
    {
        int a = fibodeque.back();
        int b = fibodeque[fibodeque.size() - 2];

        int fib_result = (a + b) % 1000000007;
        fibodeque.push_back(fib_result);
        fibodeque.pop_front();
    }

    return fibodeque.back();
}

int main()
{
    deque<int> fibodeque;
    int N;
    cin >> N;
    cout << fib(N, fibodeque) << " " << N - 2;
    return 0;
}

---

문제 풀이

​

의사코드와 문제를 유심히 보면 코드1은 피보나치의 N항째 수를, 코드2는 for문의 실행횟수를 출력한다는 것을 알 수 있다.

1, 2항을 제외하고 for문을 써서 더하므로 두번째로 출력할 값은 N-2라는걸 쉽게 알 수 있다.

 

그러나 문제는 첫번째로 출력할 값이다.

의사코드1을 그대로 구현하면 시간 초과가 뜬다.

당연히 다이나믹 프로그래밍이 적용된 의사코드2를 바탕으로 코드를 짜야한다. 

그러나 의사코드2를 vector로 그대로 구현하면 메모리 초과가 뜬다.

 

메모리 초과를 막기 위해 deque를 써서 push_back()한 후 pop_front()를 이용해 앞의 원소를 지워버리면 메모리를 아낄 수 있다.