[백준 2749] 피보나치 수 3 (C#, C++) - soo:bak

문제 링크

2749번 - 피보나치 수 3

설명

이 문제는 매우 큰 수에 해당하는 피보나치 항의 값을 특정 수로 나눈 나머지를 구하는 문제입니다.

단순히 점화식을 그대로 구현할 경우 시간과 메모리 모두 초과되므로, 수학적 성질을 활용해야 합니다.

핵심 아이디어: 피사노 주기(Pisano Period)

• 어떤 수 M으로 피보나치 수를 나눈 나머지 수열은 항상 유한한 길이의 주기를 가집니다.
• 이 주기를 피사노 주기라 하며, M = 1,000,000일 때 그 주기는 1,500,000입니다.
• 즉, 나머지 수열이 주기적으로 반복되므로 다음이 성립합니다:

\[F(N) mod M = F(N mod P) mod M\]

여기서:

• \(F(N)\): 피보나치 수의 N번째 항
• \(M\): 나눌 정수 (이 문제에서는 (1,000,000))
• \(P\): 피사노 주기 (이 문제에서는 (1,500,000))

왜 주기가 성립하는가?

피보나치 수열은 다음 점화식을 따릅니다:

\[F(n) = F(n - 1) + F(n - 2)\]

여기에 모듈로 연산을 적용하면:

\[F(n) mod M = (F(n-1) + F(n-2)) mod M = (F(n-1) mod M + F(n-2) mod M) mod M\]

즉, 피보나치 수열의 모듈로 연산 결과도 점화식의 형태를 유지합니다.

이 연산은 유한한 나머지 값들의 집합 안에서 동작하므로, 언젠가는 같은 나머지 쌍이 다시 등장하게 됩니다.

그 순간부터 수열은 주기적으로 반복되며, 그 주기가 바로 피사노 주기입니다.

따라서:

\[F(N) mod M = F(N mod P) mod M\]

이 식은 피보나치 수열의 주기성과 모듈로 연산의 닫힘성을 바탕으로 유도됩니다.

접근법

1. 피사노 주기를 활용한 입력 축소 피보나치 수를 어떤 수 M으로 나눈 나머지를 구할 때는 피사노 주기를 이용해 계산 범위를 줄일 수 있습니다.
   

   문제에서 M = 1,000,000이므로, 피사노 주기는 1,500,000입니다.
   

   따라서 F(N) % 1,000,000 = F(N % 1,500,000) % 1,000,000이므로,
   

   실제로는 N % 1,500,000번째 피보나치 수만 계산하면 됩니다.
   

2. 점화식을 이용한 반복 계산 축소된 N' = N % 1,500,000을 기준으로,
   

   피보나치 수의 기본 점화식 F(n) = F(n - 1) + F(n - 2)을 사용해 F(N')을 계산합니다.
   

   • 초기값 F(0) = 0, F(1) = 1로 시작합니다.
     
   • F(n)을 계산할 때마다 1,000,000으로 나눈 나머지를 저장합니다.
     
3. 배열을 이용한 누적 저장
   • 계산 중간의 값을 모두 저장하기 위해 크기 N' + 1의 배열을 선언합니다.
     
   • 각 인덱스에 F(i) % 1,000,000 값을 저장하므로,
     수의 크기를 제한하면서도 정확한 나머지 결과를 얻을 수 있습니다.
     
4. 최종 출력
   • 최종적으로 fibo[N'] 값을 출력하면 F(N) % 1,000,000 결과와 같습니다.
     

---

Code

[ C# ]

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      const int MOD = 1_000_000;
      const int PERIOD = 1_500_000;

      var n = ulong.Parse(Console.ReadLine()!) % PERIOD;
      var fibo = new int[n + 1];
      fibo[0] = 0;
      if (n > 0) fibo[1] = 1;

      for (ulong i = 2; i <= n; i++)
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;

      Console.WriteLine(fibo[n]);
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ull n; cin >> n;
  n %= 1'500'000;

  vi fibo(n + 1);
  fibo[0] = 0;
  fibo[1] = 1;
  for (ull i = 2; i <= n; i++) {
    fibo[i] = fibo[i - 1] + fibo[i - 2];
    fibo[i] %= 1'000'000;
  }

  cout << fibo[n] << "\n";

  return 0;
}