[백준/BOJ] 30824번 피보나치 더하기 (C++)

개요

이 글은 백준 30824번 피보나치 더하기 문제를 풀이한다.

요약

$k$와 $x$을 입력받아 $k$개의 피보나치 수열의 항들을 더하여 $x$를 만들 수 있는지 판별하라.

입력 조건

$1 \leq k \leq 3$

$1 \leq x \leq 10^{16}$

분석

피보나치 수열은 다음과 같이 정의된다.

\[F_{n} = \begin{cases} 1 & \text{if } n = 1, 2 \\ F_{n-1} + F_{n-2} & \text{if } n \geq 3 \end{cases}\]

입력 조건을 분석해보면, 미리 계산해야 하는 피보나치 수열의 항은 $10^{16}$보다 작은 수이다. 따라서 이 문제에서는 long long 자료형을 사용해도 무방하다.

풀이

미리 계산해야 하는 피보나치 수열의 범위를 계산해보면, 최대 $F_{78} = 8,944,394,323,791,464$까지 구하면 된다. 다음으로, $k$의 값에 따라 모든 경우를 확인하면 된다.

예시 답안

#include <iostream>
#include <vector>
using namespace std;

vector<long long> precompute(void) {
  vector<long long> f(79);
  f[1] = 1; f[1] = 1;
  for (int i = 3; i <= 78; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f;
}

bool solve(vector<long long>& f) {
  long long k, x; cin >> k >> x;

  if (k == 1) {
    for (int i = 1; i <= 78; i++) {
      if (f[i] == x) return true;
    }
  } else if (k == 2) {
    for (int i = 1; i <= 78; i++) {
      for (int j = 1; j <= 78; j++) {
        if (f[i] + f[j] == x) return true;
      }
    }
  } else {
    for (int i = 1; i <= 78; i++) {
      for (int j = 1; j <= 78; j++) {
        for (int l = 1; l <= 78; l++) {
          if (f[i] + f[j] + f[l] == x) return true;
        }
      }
    }
  }
  return false;
}

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

  vector<long long> f = precompute();

  int t; cin >> t;
  while (t--) cout << (solve(f) ? "YES" : "NO") << "\n";
  return 0;
}

원본 소스 코드는 Hiyabye/Baekjoon - 30824.cpp 에서 확인할 수 있다.

문제 해결 팁

재귀를 이용한 피보나치 수열 구현은 시간복잡도가 $\mathcal{O}(2^N)$으로 매우 느리다. 따라서 이 방법은 사용하지 않는 것이 좋다.

반복문을 이용한 DP를 사용하여 피보나치 수열을 구현하면 시간복잡도가 $\mathcal{O}(N)$으로 훨씬 빠르다.

마무리

도움이 되었다면 반응이나 댓글을 남겨주시면 감사하겠습니다.

추가적인 의견이나 피드백 또한 언제든지 환영입니다! :)