백준 1003번 - 피보나치 함수

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

피보나치 함수 문제로 재귀 호출을 통해 0 또는 1 까지 가게 되면 값을 리턴해주는 형식이다.

그러나 문제에 나와 있는 것처럼 피보나치 함수를 그대로 적용하면 시간 초과가 걸린다.

예전에 이 문제를 어떻게 풀까 고민하다가 DP 방식으로 구현을 하지 못해서 해결하지 못했는데

이번에 다시 풀어보니깐 생각보다 쉽게 풀렸다.

접근 방법은 각각의 숫자 별로 0과 1의 값이 몇 개인지 구하는 방식이다.

점화식은 다음과 같다.

dp[n][0]= n번째 숫자에서 0을 호출한 횟수

dp[n][1]= n번째 숫자에서 1을 호출한 횟수

그렇다면 dp[0][0] 과 dp[1][1] 값은 자연스럽게 1이 될 것이다.

다음으로 

dp[2][0] 은 dp[1][0]+dp[0][0] 이 되고

dp[2][1]은 dp[1][1]+dp[0][1]이 된다.

이를 N 번째 까지 수행하면

N 번째에서 0과 1이 몇 번 호출되는지 알 수 있다.

#include <iostream>
using namespace std;
 
 
int main(){
    
    int T;
    cin>>T;
    
    int N;
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d",&N);
        
        int dp[41][2]={0};
        dp[0][0]=dp[1][1]=1;
        
        for(int i=2;i<=N;i++){
            dp[i][0]=dp[i-1][0]+dp[i-2][0];
            dp[i][1]=dp[i-1][1]+dp[i-2][1];
        }
        
        printf("%d %d\n",dp[N][0],dp[N][1]);
    }
    return 0;
}