BOJ 1003번 피보나치 함수

BOJ : https://www.acmicpc.net/problem/1003

github : https://github.com/junho0956/Algorithm/blob/master/1003/1003/%EC%86%8C%EC%8A%A4.cpp

 

dp[n] 의 의미는 n 일때 0 과 1 의 호출 횟수를 담는 pair 배열입니다.

다음 재귀문과 같이 동적계획법을 이용하여 문제를 해결합니다.

 

#include <iostream>
using namespace std;
 
typedef pair<long long, long long> ll;
 
ll dp[41];
 
ll solve(int num) {
    if (num == 0) return { 1,0 };
    if (num == 1) return { 0,1 };
 
    if (num < 0) return{ 0,0 };
 
    ll& res = dp[num];
    if (res.first || res.second) return res;
 
    ll ans = solve(num - 1);
    ll ans2 = solve(num - 2);
    return res = { ans.first + ans2.first, ans.second + ans2.second };
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        ll ans = solve(n);
        cout << ans.first << " " << ans.second << "\n";
    }
 
    return 0;
}