[BOJ/C++] 피보나치 함수(1003번)

1. 개요

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

1003번: 피보나치 함수

1-1. 설명

N번째 피보나치를 구하게 된다면 재귀를 통해 0부터 N의 피보나치 값들이 구해지게 될 것이다. 여기서 fibonacci(N) 함수를 호출했을 때, 0과 1이 각각 몇번 출력되는지 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 테스트 케이스 개수 T가 주어짐

 - 각 테스트 케이스는 한줄로 이루어져 있으며, N이 주어짐

 - N은 40 이하 자연수 or 0

---

2. 구현

2-1. 풀이

DP의 bottom-up 방식을 이용해 풀어야겠다고 생각했다. 간략하게 표를 살펴보자

0과 1 도출

위의 표처럼 0과 1의 개수를 나타낼 수 있다. 여기서 그럼 점화식은 dp[i] = dp[i-1] + dp[i-2] 임을 알 수 있다. 이전값 2개를 더해 현재값을 구하면 된다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[41][2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T, num;
    cin >> T;
    dp[0][0] = 1, dp[1][1] = 1;
    int index = 2;
    for (int tc = 0; tc < T; tc++) {
        cin >> num;
        if (num >= 2) {
            for (int i = index; i <= num; i++) {
                dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
                dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
            }
            index = num + 1;
        }
        cout << dp[num][0] << ' ' << dp[num][1] << "\n";
        
    }

    return 0;
}