[백준 24417번] 알고리즘 수업 - 피보나치 수 2 (C++)

문제링크 : https://www.acmicpc.net/problem/24417

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

const int MOD = 1000000007;
int N;

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

    cin >> N;
    ll a = 1, b = 1; //더할 값 2가지
    for(int i=2; i<N; i++)
    {
        ll tmp = (a + b)%MOD; //더하고 나온 값
        swap(a, b); //하나씩 앞으로 댕기기
        swap(b, tmp);
    }
    cout << b << " "<< N-2;    

    return 0;
}

 

언듯보면 웰노운으로 잘 알려진 dp 식을 이용해 피보나치를 푸는 문제이다.

하지만 이렇게 풀 경우 N의 값이 최대 1억이기에 여기에만 메모리가 400MB가 사용되고,

DP 중간 계산과정에서 추가적인 메모리를 사용하기에 주어진 메모리 값인 512MB를 초과하는 경우가 발생할 수 있다.

 

따라서 직접 더할 값 2가지와, 더한 값을 저장할 결과 값 1개를 선언해준다.

이후 뒤 쪽에 해당하는 값 2가지 (2번 째 더할 값과 더하고 나온 결과 값) 을 앞으로 땡겨주고, 또 해당 값을 앞에 방법과 동일하게 반복하여 더해나가며 값을 갱신해 나가면 된다.

 

문제에 주어진 return 1에 대한 값은 해당 값을 통해 피보나치 연산한 결과값이 나오기 때문에 최종 연산된 b의 값이라고 할 수 있다.

그리고 fibo(n-1) + fibo(n-2)는 계산과정에 해당하므로 우리가 구현한 반복문의 실행 횟수라고 할 수 있다.