[백준 15841] Virus Outbreak (C#, C++) - soo:bak

문제 링크

15841번 - Virus Outbreak

설명

시간 t가 주어질 때 감염된 소의 수를 출력하는 문제입니다. 감염 소의 수는 피보나치 수열을 따릅니다.

접근법

시간 t에서의 감염 소 수는 F(t)이며, 피보나치 점화식 F(n) = F(n-1) + F(n-2)를 따릅니다.

t가 최대 490까지 가능하므로 매우 큰 수가 됩니다. C#에서는 BigInteger를 사용하고, C++에서는 문자열로 각 자릿수를 저장해 덧셈을 구현합니다.

미리 1부터 490까지의 피보나치 수를 계산해 배열에 저장한 뒤, 입력마다 바로 출력합니다.

---

Code

C#

using System;
using System.Numerics;

class Program {
  static void Main() {
    var fib = new BigInteger[491];
    fib[1] = 1;
    fib[2] = 1;
    for (var i = 3; i <= 490; i++)
      fib[i] = fib[i - 1] + fib[i - 2];

    string? line;
    while ((line = Console.ReadLine()) != null) {
      var t = int.Parse(line);
      if (t == -1) break;
      Console.WriteLine($"Hour {t}: {fib[t]} cow(s) affected");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

  const int MAXN = 490;
  vector<string> fib(MAXN + 1);
  fib[1] = "1";
  fib[2] = "1";

  auto add = [](const string& a, const string& b) {
    string res;
    int i = (int)a.size() - 1, j = (int)b.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
      int sum = carry;
      if (i >= 0) sum += a[i--] - '0';
      if (j >= 0) sum += b[j--] - '0';
      res.push_back(char('0' + (sum % 10)));
      carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
  };

  for (int i = 3; i <= MAXN; i++)
    fib[i] = add(fib[i - 1], fib[i - 2]);

  int t;
  while (cin >> t && t != -1)
    cout << "Hour " << t << ": " << fib[t] << " cow(s) affected\n";

  return 0;
}