백준 2749번 C, C++ 풀이

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

2749번: 피보나치 수 3

 

n이 정말 살벌한 문제. 그렇다고 n의 최댓값만큼 배열을 저장했다가는 램이 터질 문제. 이 문제를 어떻게 접근해야하나 싶어서 처음에는 일반항으로 접근해서 모듈러연산을 수행하려고 했지만, 나누려는 대상이 정수가 아니라서 실패했다.

 

그래서 어떻게 할까 하다가, 저번에 풀었던 피사노 주기 문제가 생각났다. (https://codejin.tistory.com/118)

 

피사노 주기의 성질에서 m = 10^n (n>2)일때 피사노 주기K(m)은 15 * 10^(n-1)이다. 이때 나누는 숫자가 100만, 즉 10^6이므로 피사노 주기는 K(10^6) = 150만이다. 이 말은 즉, 150만마다 값이 반복된다는 뜻이므로, 피보나치 수열을 100만으로 나눈 값을 150만개를 저장한다. 이때 피보나치 수열은 숫자가 기하급수적으로 커지므로, 모듈러 연산을 통해 나머지만 남긴다.

 

// C
#include <stdio.h>
#define SIZE 1500000
#define MOD 1000000

int main () {
    long long n;
    int arr[SIZE] = {0, 1};

    for (int i = 2; i < SIZE; i++)
        arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
    scanf("%lld", &n);
    printf("%d", arr[n % SIZE]);
}

 

// C++
#include <iostream>
#define SIZE 1500000
#define MOD 1000000
using namespace std;


int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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];
}

 

위 : C++, 아래 : C