Beakjoon 1003 피보나치 함수

18 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1003

나의 풀이

기존 피보나치 수열의 점화식인 DP[i] = DP[i-1] + DP[i-2]를 0과 1 둘로 구분하여 문제를 해결한다.
DP[i][0] = i번째에서 0이 불리는 경우
DP[i][1] = i번째에서 1이 불리는 경우

DP[0][0] = 1, DP[0][1] = 0
DP[1][0] = 0, DP[1][1] = 1

DP[i][0] = DP[i-1][0] + DP[i-2][0]
DP[i][1] = DP[i-1][1] + DP[i-2][1]

풀이 코드 : 1003 피보나치 함수

#include <iostream>
#include <vector>

using namespace std;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin>>N;
    int DP[41][2];

    vector<int> arr;    
    arr.resize(N);
    for(int i=0;i<N;i++){
        cin>>arr[i];
    }
    DP[0][0] = 1;
    DP[0][1] = 0;

    DP[1][0] = 0;
    DP[1][1] = 1;
    
    for(int i=2;i<=40;i++){
        DP[i][0] = DP[i-1][0] + DP[i-2][0];
        DP[i][1] = DP[i-1][1] + DP[i-2][1];
    }

    for(int i=0;i<N;i++){
        cout<<DP[arr[i]][0]<<" "<<DP[arr[i]][1]<<"\n";
    }
}

채점결과