[C/C++] 백준 2749번 - 피보나치 수 3

✏️  문제 링크

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

 

✏️ 문제 설명

 

✏️ 로직

엉첨 머리를 싸맸는데 생각보다 간단했다. ⇒ 피사노 주기라는 걸 알게 됨

1. 피사노 주기
2. m이 10의 n승일 때 피사노 주기는 15 * 10^(n-1)
3. m이 10의 6승이므로 피사노 주기는 15 * 10^(5) = 1500000
4. 즉 피보나치 수열을 1500000번째까지만 구해서 배열에 저장 후 arr[n%1000000]을 출력

✏️ 코드

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

#define SIZE 1500000
#define MOD 1000000

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned long long int n;
    int arr[SIZE] = {0, 1};

    for (int i = 2; i < SIZE; i++)
        arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;

    cin >> n;
    cout << arr[n % SIZE];

}

 

✏️ 느낀 점

머 이렇게 간단하냐;;;;

난이도는 골드2지만 피사노 주기라는 걸 아는 상태에서 접한다면 그냥 브론즈 수준의 문제일 것 같다.

 

✏️ 결과

시간복잡도

O(SIZE) ⇒ O(1500000)이므로 시간 초과가 발생하지 않는다.