[Algorithm]Baekjoon 15624번 : 피보나치 수 7

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

15624번: 피보나치 수 7

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int mod = 1000000007;
int n;
int arr[3] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    if (n == 0)
    {
        cout << 0;
        return 0;
    }
 
    arr[0] = 0;
    arr[1] = 1;
 
    int first = 0;
    int second = 1;
    int result = 2;
 
    for (int i = 0; i < n+1; ++i)
    {
        arr[result] = (arr[first] % mod + arr[second] % mod) % mod;
 
        first = (first + 1) % 3;
        second = (second + 1) % 3;
        result = (result + 1) % 3;
    }
 
    cout << arr[result];
}

 

간단한 피보나치문제인데, n값이 100만이라서 그냥 100만크기의 int형 배열을 선언해서 fibonacci[n] = fibonacci[n-1] + fibonacci[n-2]  이렇게 풀어도 된다.

 

근데 사실 계산할때마다 n-1번째랑 n-2번째만 필요하기 때문에 그냥 크기 3짜리 int형 배열로도 충분히 문제가 풀린다.

처음에는 0번째 인덱스와 1번째 인덱스를 n-1번째값인덱스,n-2번째값 인덱스로 사용하고 n값을 2번쨰인덱스에 저장한다.

그다음에는 각각의 인덱스값(first,second,result)을 +1씩 해주고 3으로 나눠주면, 한칸씩 칸이 밀리기 때문에 또 재활용해서 쓸 수 있는 것이다.