백준 1003 피보나치 함수 C++ [컴공과고씨의 개발일지]

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

1003번: 피보나치 함수

이 문제를 처음 보고 위 보기에 있는 코드를 써서 카운트를 한다면 아마 시간초과가 날 것이다. 재귀 함수는 기본적으로 시간을 많이 쓰기 때문에...

그렇기에 다른 방법을 사용해야 하는데 나는 동적 계획법을 사용하여 풀었다.

동적 계획법은 이제 처음 연산은 기록해서 이미 했던 연산일 경우 연산을 하지않고 기록한 값을 가져오는 방식으로 위 문제를 재귀함수로 푸는 것 보다 훨씬 빠르다.

 

원리는 

             0                                                          1

f(0)  =   1번                                                       0번

f(1)  =   0번                                                       1번

f(2)  =   f(0)의 0번 개수 + f(1)의 0번 개수, f(0)의 1번 개수 + f(1)의 1번 개수

f(3)  =   f(2)의 0번 개수 + f(1)의 0번 개수, f(2)의 1번 개수 + f(1)의 1번 개수

이런 식으로 쭉 갈건데 여기서 f(2)의 0번 개수와 1번 개수를 구할 때 재귀 함수로 연산을 실행하지 않고 그 전에 배열에 값을 저장해주고 그 값을 불러오는 형식으로 구현해 주면 된다.

 

전체코드

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int t,n;
    vector<pair<int, int>> ans;
    cin >> t; 
    for (int T = 0; T < t; T++){
        cin >> n;
        int dp[2][41];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1; // 초기값 설정
 
        for (int i = 2; i <= n;i++){
            dp[0][i] = dp[0][i - 1] + dp[0][i - 2]; //0번 개수 저장
            dp[1][i] = dp[1][i - 1] + dp[1][i - 2]; //1번 개수 저장
        }
 
        ans.push_back(make_pair(dp[0][n], dp[1][n]));
    }
 
    for (int i = 0; i < ans.size();i++){
        cout << ans[i].first << " " << ans[i].second << '\n';
    }
    return 0;
}

 

사용문법 : 동적계획법

 

yea!