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

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

문제

입출력

문제 접근

dp문제이다. 규칙을 찾으면 된다. 나는 0과 1이 각각 피보나치를 이루고 있어서, 그것을 규칙을 두고 풀었다. 하지만, 다른 사람들 풀이를 봤을 때, 0과 1을 각각 생각하는 것이 아닌, 같이 피보나치 수열을 있다고 보았고, 1은 dp[n]을 출력하면 되고, 0은 dp[n-1]을 출력하면 된다.

코드 구현(c++)

#include <iostream>

using namespace std;
int cacheZero[41];
int cacheOne[41];
void cal(int num){
    for(int i = 2 ; i <= num ; i++){
        cacheZero[i] = cacheZero[i-1] + cacheZero[i-2];
        cacheOne[i] = cacheOne[i-1] + cacheOne[i-2];
    }
    cout << cacheZero[num] << " " << cacheOne[num] << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cacheZero[0] = 1; cacheZero[1] = 0;
    cacheOne[0] = 0; cacheOne[1] = 1;
    int testCase;
    cin >> testCase;
    int num;

    for(int i = 0 ; i < testCase ; i++){
        cin >> num;
        cal(num);    
    }
}