1003번: 피보나치 함수

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

구현 아이디어 5분 구현 10분

풀이

fibonacci(n - 1) + fibonacci(n - 2) 피보나치 같이 0과 1의 개수도 fibonacci(n - 1)의 0, 1의 개수 + fibonacci(n - 2)의 0, 1의 개수이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// N은 40보다 작거나 같은 자연수 또는 0.
// 다이나믹.
int Dp[41][2];    // 0: 0 개수, 1: 1개수.

int main()
{
    // 0이 가지는 0과 1의 개수.
    Dp[0][0] = 1;
    Dp[0][1] = 0;
    
    // 1이 가지는 0과 1의 개수.
    Dp[1][0] = 0;
    Dp[1][1] = 1;
    
    for(int i = 2; i <= 40; ++i)
    {
        // Dp 만들기.
        Dp[i][0] = Dp[i - 1][0] + Dp[i - 2][0];
        Dp[i][1] = Dp[i - 1][1] + Dp[i - 2][1];
    }
    
    int T = 0;
    scanf("%d", &T);
    for(int i = 0; i < T; ++i)
    {
        int N = 0;
        scanf("%d", &N);
        
        printf("%d %d\n", Dp[N][0], Dp[N][1]);
    }
    
    return 0;
}