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

문제 링크

2748번 - 피보나치 수 2

설명

이 문제는 보다 큰 수 범위의 피보나치 수를 계산해야 하므로, 자료형 선택이 중요한 문제입니다.

피보나치 수열은 다음의 점화식으로 정의됩니다:

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

단, \(F(0) = 0\) , \(F(1) = 1\)

---

차이점: [백준 2747]과의 비교

• 2747번 - 피보나치 수 문제는 int 범위 내에서 처리가 가능하지만,
  

  본 문제는 n ≤ 90으로 F(n)이 long 범위까지 증가하므로 int 자료형에서는 오버플로우가 발생할 수 있습니다.
  
  

• 따라서, C++ 에서는 long long, C# 에서는 long 자료형을 사용해야 합니다.

---

접근법

• 크기 n + 1인 배열을 만들고, fibo[0] = 0, fibo[1] = 1로 초기화합니다.
• 반복문을 통해 2부터 n까지 차례대로 값을 채워나갑니다.
• 점화식에 따라 이전 두 항의 합을 누적하며 저장하고, 마지막에 fibo[n]을 출력합니다.

---

Code

[ C# ]

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      int n = int.Parse(Console.ReadLine()!);
      var fibo = new long[n + 1];
      fibo[0] = 0;
      fibo[1] = 1;

      for (int i = 2; i <= n; i++)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

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

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<ll> vll;

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

  int n; cin >> n;
  vll fibo(n + 1);
  fibo[0] = 0;
  fibo[1] = 1;
  for (int i = 2; i <= n; i++)
    fibo[i] = fibo[i - 1] + fibo[i - 2];

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

  return 0;
}