백준 1003번: 피보나치 함수

다이나믹 프로그래밍을 이용해 해결하는 문제다.

재귀함수를 쓰는 방법과 다르게 다이나믹 프로그래밍을 이용하는 방법은
재귀적 방법을 사용하되 불필요한 계산은 제거하는 방식이다.

1. 배열의 값을 전부 0으로 초기화후 1번째 원소만 1로 초기화를 해준다.

2. 함수 실행

2. 1 입력값이 n = 0일때 => 1 0
2. 2 입력값이 n = 1일때 => 0 1
2. 3 입력값이 n >= 2 일 때

2. 3. 1   배열 n의 값이 0이라면
피보나치 함수를 사용해 계산한다.
계산 결과를 n번째 원소의 값으로 넣고 리턴한다.
2. 3. 2   배열 n의 값이 0이 아니라면
0이 아닌 이유는 이전에 계산결과를 배열에 저장해 두었기 때문이다.
따라서, 이 경우에는 피보나치 함수를 다시 하지 않고 배열의 값을 꺼내 쓴다.
이러면, 불필요한 계산을 하지 않게된다.

결과
0의 개수는 배열의 n-1번째 원소와 같고 1의 개수는 배열의 n번째 원소와 같다.

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

#include <iostream>
using namespace std;

int arr[41] = {0, 1, 0,};

int fib(int a)
{
    if(a == 0)
    {
        arr[a] = a;
        return a;
    }
    else if(a == 1)
    {
        arr[a] = a;
        return a;
    }
    if(arr[a] != 0)
    {
        return arr[a];
    }
    else
    {
        return arr[a] = fib(a - 1) + fib(a - 2);
    }
}

int main()
{
    int size;
    cin >> size;
    int num;
    for(int i = 0; i < size; i++)
    {
        cin >> num;
        if(num == 0)
            cout << 1 << " " << 0 << endl;
        else if(num == 1)
            cout << 0 << " " << 1 << endl;
        else{
            fib(num);
            cout << arr[num - 1] << " " << arr[num] << endl;
        }
    }
}