BOJ - 피보나치 함수(1003)

실버3 : 동적 계획법을 사용하는 문제이다.

Code

// 백준 1003번 피보나치 함수
#include <iostream>
using namespace std;
int N = 0, T = 0;
int dp[50] = {0};
// dp[n] = an 까지의 호출되는 1의 개수
// dp[n] = dp[n-2] + dp[n-1];
// 호출되는 0의 개수는, dp[n-1]과 동일하다.
 
int main(){
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i < 41; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        cin >> N;
        if (N == 0) cout << 1 << " " << dp[N] << '\n';
        else        cout << dp[N-1] << " " << dp[N] << '\n';
    }
}
 

Reference

• 백준(1003번) - 피보나치 함수