백준 - 피보나치 수 3 (C++)

Pixabay로부터 입수된 Mehmet Turgut Kirkgoz님의 이미지 입니다.

 

---

 

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

9471번: 피사노 주기

 

 이번 문제는 숫자 n이 주어질 때, n번째 피보나치 수를 1,000,000으로 나눈 값을 구하는 문제이다. 처음에는 단순히 재귀나 반복문을 이용해서 구하면 될 것 같다고 생각했다. 하지만 n의 조건을 보니 그렇게 단순한 문제는 아니라는 것을 알게 되었다. n은 최대 1,000,000,000,000,000,000(1경)이다. 만약 반북문을 이용할 경우 최대 1경번 반복문을 실행해야 할 수 있다.

 더 좋은 방법이 없을까 고민하던 중, 피사노 주기라는 게 있다는 것을 알았다. 피사노 주기는 백준의 9471번(피사노 주기) 문제에서도 확인할 수 있다. 이 문제에는 피사노 주기와 관련된 공식이 있다. 그 중 'n > 2라면, k(10n) = 15×10(n-1)' 이 공식을 이 문제에 적용할 수 있을 것 같다. 이 문제는 1,000,000으로 나눈 값을 구하는 문제이므로, k(1,000,000) = 1,500,000 이다. 즉, n이 1,500,000 이하라면 그대로 1,500,000번째의 피보나치 수에 1,000,000을 나눈 값을, 1,500,000 초과라면 n을 1,500,000으로 나눈 나머지에 해당하는 값의 피보나치 수를 출력하면 된다. 다음은 대략적인 의사 코드이다.

 

1. 1부터 1,500,000까지의 나머지 값(피보나치 수를 1,000,000으로 나눈 값의 나머지)을 저장한다.
2. n을 입력받는다.
3. n을 1,500,000으로 나눈 나머지 값을 n에 다시 저장한다.
4. 이 n에 해당하는 나머지 값을 출력한다.

 

#include <iostream>
#pragma warning(disable:4996)
#define MOD 1000000
#define LEN 1500000

using namespace std;

long long n;
int record[LEN];

void Record()
{
    int bef = 0;
    int cur = 1;

    record[0] = 0;
    record[1] = 1;

    for (int i = 2; i <= LEN; ++i)
    {
        int temp = bef;
        bef = cur;

        cur = (cur + temp) % MOD;

        record[i] = cur;
    }
}

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

    Record();

    cin >> n;
    n %= LEN;

    cout << record[n] << endl;
    
    return 0;
}

---

참고

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

9471번: 피사노 주기