[BOJ_C++] 1003번 : 피보나치

# 문제

---

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

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

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

    int t, n; cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> n;
        if (n == 0)
            printf("1 0\n");
        else
            printf("%d %d\n", d[n-1], d[n]);
    }

    return 0;
}

• 제한시간이 매우 짧기 때문에 재귀함수를 사용하여 문제를 해결하면 시간초과가 나오게 된다.
• 따라서 다이나믹 프로그래밍을 사용해야 한다. 다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘으로 위 문제와 같은 문제에서 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 땐 이미 저장되어 있는 값을 반환하기만 하면 된다.

---

• 테스트케이스의 개수를 입력받기 전에 먼저 피보나치 40까지의 값을 배열에 미리 계산해 두었다.
• 각 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분하여 출력해야 하는데 이때 0이 출력되는 횟수와 1이 출려되는 횟수는 피보나치[n-1], 피보나치[n]과 같다.

피보나치[n]	피보나치 값	0의 개수	1의 개수
0	0	1	0
1	1	0	1
2	1	1	1
3	2	1	2
4	3	2	3
5	5	3	5
n	피보나치[n-1] + 피보나치[n-2]	피보나치[n-1]	피보나치[n]

• 즉, n이 0인 경우를 제외하고는 미리 계산해 둔 피보나치[n-1] 피보나치[n] 값을 출력해주면 된다.

---

# 결과