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

문제 링크

2747번 - 피보나치 수

설명

0번째와 1번째 수가 각각 0과 1로 정의된 피보나치 수열의 N번째 수를 구하는 문제니다.

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

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

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

문제의 범위가 작기 때문에 재귀가 아닌 반복문 방식으로 해결하는 것이 더 효율적입니다.

---

접근법

• 크기가 n + 1인 배열을 만들어 피보나치 값을 저장합니다.
• 초기값 F(0) = 0, F(1) = 1을 먼저 설정합니다.
• 2부터 n까지 반복문을 돌며 점화식을 기반으로 값을 계산합니다.
• 마지막으로 배열의 n번째 원소를 출력합니다.

---

Code

[ C# ]

using System;
using System.Linq;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      int n = int.Parse(Console.ReadLine()!);
      var fibo = new int[n + 1];
      fibo[0] = 0;
      if (n > 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 vector<int> vi;

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

  int n; cin >> n;

  vi 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;
}