[백준 1003번] 피보나치 함수 C++

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

진짜 죽어도 DP로 풀고싶었다

이거 풀이보니까 뭐 0과 1이 나오는 표인가 이런거있던데 이런거말고..

 

풀이법은 부분에서 나온 0과 1 이 출력된 횟수를 메모이제이션하고

각각의 부분에서 나온 횟수를 더하면 n의 0과 1이 출력된 횟수가 나온다고 짰다

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
//0과 1을 구하는 횟수를 메모이제이션
int dp[2][41];
int save;
 
void fibonacci(int a) {
 
    for (int i = 2; i <= a; i++) {
        dp[0][i] = dp[0][i - 1] + dp[0][i - 2];
        dp[1][i] = dp[1][i - 1] + dp[1][i - 2];
    }
}
 
int main() {
    
    int t;
    cin >> t;
 
    dp[0][0] = 1;
    dp[1][1] = 1;
 
    while (t--) {
        
        int n;
        cin >> n;
        save = n;        
        fibonacci(n);
        cout << dp[0][n] << " " << dp[1][n] << "\n";
    }
    return 0;
}

풀었다 !!!!!!!!!!!!!