[1003] 피보나치 함수(C++)

---

 

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

1003번: 피보나치 함수

 

 

🔎 해결 방법 

fibo(n) = fibo(n-1) + fibo(n-2) 인 것과 마찬가지로

0과 1이 출력되는 횟수도 이전의 두 개를 더해주면 된다.

 

즉, 점화식은

1. dp[n][0] = dp[n-1][0] + dp[n-2][0]

2. dp[n][1] = dp[n-1][1] + dp[n-2][1] 

이렇게 두 가지를 사용하면 된다.

 

 

💡내 코드(C++) 

// [1003] 피보나치 함수
// https://www.acmicpc.net/problem/1003

#include <iostream>
using namespace std;

int main(void)
{
    int t, n, dp[40][2];
    cin >> t; 
    dp[0][0] = 1, dp[0][1] = 0;
    dp[1][0] = 0, dp[1][1] = 1;
    
    for(int i = 0 ; i < t ; i++) {
        cin >> n;
        
        for(int j = 2 ; j <= n ; j++) {
            dp[j][0] = dp[j-1][0] + dp[j-2][0];
            dp[j][1] = dp[j-1][1] + dp[j-2][1];
        }
        
        cout << dp[n][0] << " " << dp[n][1] << endl;
    }
}