백준 1003번 : 피보나치 함수

• 분류: 다이나믹 프로그래밍

코드

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

int n;
vector<pair<int, int>> dp;

pair<int, int> fib(int p) {
    if(p==0) {
        pair<int, int> result = pair<int, int>(1, 0);
        return result;
    }
    else if(p==1) {
        pair<int, int> result = pair<int, int>(0, 1);
        return result;
    }
    else {
        if(dp[p].first==-1) {
            pair<int, int> p1 = fib(p-1);
            pair<int, int> p2 = fib(p-2);
            pair<int, int> result = pair<int, int>(p1.first+p2.first, p1.second+p2.second);
            dp[p] = result;
            return result;
        }
        else {
            return dp[p];
        }
    }
}

int main() {
   cin >> n;

   for(int i=0 ; i<n ; i++) {
       int k;
       cin >> k;
       for(int j=0 ; j<=k ; j++) {
           dp.emplace_back(-1, -1);
       }
       pair<int, int> result = fib(k);
       cout << result.first << ' ' << result.second << '\n';
   }
}

• 코멘트
  
  피보나치는 익숙하지만, 이 문제는 살짝 꼬아서 피보나치 수를 구하는 게 아니라 fib(0)과 fib(1)이 불린 횟수를 묻는다.
  그래도 크게 달라지지는 않는다. pair를 사용해서 fib(0)과 fib(1)이 불린 횟수를 한번에 관리할 수 있다.
  물론 규칙이나 일반항을 찾으면 훨씬 간단하게 되겠지만.. 그냥 dp의 의의에 맞게 고지식하게 풀어 보았다.