[백준 1003] 피보나치 함수

피보나치 함수

문제 설명

피보나치 함수에서 0과 1이 각각 출력 되는지 결과 값을 출력한다.
이때 T의 수만큼 테스트케이스를 반복하고 N(40까지)의 값을 각각 입력 받는다.

알고리즘

1. 배열에 40까지의 예측 값을 저장해 둔다.
2. 테스트케이스와 0일때 1일때 그 외일 때의 경우로 나누어 출력한다.

---

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


int main()
{    
    int T, N;
    cin >> T;
    int arr[41] = {0,1,1};

    for (int i = 3; i < 41; i++)// 값 생성
        arr[i] = arr[i - 1] + arr[i - 2];
    while (T)
    {
        cin >> N;

        if (N == 0)
            cout << 1 << " " << 0 << "\n";
        else if (N == 1)
            cout << 0 << " " << 1 << "\n";
        else//2부터의 경우 출력
            cout << arr[N-1] << " " << arr[N] << "\n";
        T--;
    }

    return 0;
}

---

고찰

다이나믹 프로그래밍 문제는 많이 풀어보지 않았고, 매우 막막해서 함수를 직접 실행시켜 보았다. 코드에 직접 실행시키면 40까지 돌리는데 시간 초과가 나기때문에 값을 따로 저장해서 처리 할 필요가 있다.
결과적으로 규칙이 있기 때문에 배열에 값을 넣고 출력만 하면 풀 수 있는 문제였다.

---

풀이 규칙

N의 값	0 호출 수	1 호출 수
0	0	1
1	1	0
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13

표를 확인해 보면 N=0, N=1일때를 제외하고 규칙을 확인할 수 있다.
-> 0의 호출수 : 전의 N값의 1호출수
-> 1의 호출수 : 전의 N값의 0호출수+1호출수

따라서 배열에 미리 값을 1의 호출 수 기준으로 넣어 놓으면 N번째 배열의 값과 N-1번째의 값을 출력시키면 값을 구할 수 있다.