[백준 24416] 알고리즘 수업 - 피보나치 수 1 (C#, C++) - soo:bak

문제 링크

24416번 - 알고리즘 수업 - 피보나치 수 1

설명

피보나치 수를 재귀와 동적 프로그래밍 두 가지 방식으로 구할 때, 각 방식에서 특정 코드가 몇 번 실행되는지 구하는 문제입니다.

접근법

재귀 호출에서 코드1은 n이 1 또는 2일 때 실행됩니다. fib(5)를 호출하면 fib(4)와 fib(3)을 호출하고, 이들이 다시 더 작은 값을 호출하다가 결국 fib(1)이나 fib(2)에 도달합니다. 이렇게 기저 조건에 도달하는 총 횟수가 코드1 실행 횟수인데, 이 값은 n번째 피보나치 수와 같습니다. 예를 들어 fib(5)에서 코드1은 5번 실행되고, F(5) = 5입니다.

동적 프로그래밍에서 코드2는 for 루프 안에서 i가 3부터 n까지 돌 때 실행되므로 총 n-2번입니다. n이 5이면 i가 3, 4, 5일 때 실행되어 3번입니다.

따라서 DP로 F(n)을 구한 뒤, F(n)과 n-2를 출력하면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var dp = new int[n + 1];
    dp[1] = dp[2] = 1;
    for (var i = 3; i <= n; i++)
      dp[i] = dp[i - 1] + dp[i - 2];

    var code1 = dp[n];
    var code2 = n - 2;
    Console.WriteLine($"{code1} {code2}");
  }
}

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 dp(n + 1, 0);
  dp[1] = dp[2] = 1;
  for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

  cout << dp[n] << " " << (n - 2) << "\n";

  return 0;
}