[C++] BOJ (백준) 1003 : 피보나치 함수

문제

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

코드

#include <iostream>

#pragma clang diagnostic push
#pragma ide diagnostic ignored "ArrayIndexOutOfBounds"
#define MAX_N 40

using namespace std;

int dpZero[MAX_N + 1];
int dpOne[MAX_N + 1];

int getZero(int n) {
  if (n == 0) return 1;
  if (n == 1) return 0;
  if (dpZero[n]) return dpZero[n];
  return dpZero[n] = getZero(n - 1) + getZero(n - 2);
}

int getOne(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (dpOne[n]) return dpOne[n];
  return dpOne[n] = getOne(n - 1) + getOne(n - 2);
}

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

  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << getZero(n) << ' ' << getOne(n) << '\n';
  }
  return 0;
}

#pragma clang diagnostic pop

설명

fibonacci(N)을 호출했을 때 0과 1을 출력하는 횟수는 fibonacci(N-1)에서의 횟수 + fibonacci(N-2)에서의 횟수와 같다.
즉, DP를 사용해 해결할 수 있다.