백준 1003번 피보나치 함수(DP 사용)

문제 링크입니다:https://www.acmicpc.net/problem/1003

algospot에서 동적계획법 문제를 풀다보니 아직 미흡한 것 같아서 백준 온라인 저지에서 동적계획법 기초 문제를 풀어봤습니다. 

물론 동적계획법을 사용하지 않아도 되는 문제이지만 동적계획법을 연습하고자 메모이제이션을 사용하였습니다.

/*

N이 주어졌을 때, fibonacci(N)을 호출할 경우 0과 1이 각각 몇번 출력되는가?

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int N; //주어진 숫자

int save = 2; //이미 구한 수는 다시 구하지 않는다

int cache[2][41]; //메모이제이션

 

void fibonacci(int n)

{

        if (N >= save)

        {

               for (int i = save; i <= N; i++)

               {

                       cache[0][i] = cache[0][i - 1] + cache[0][i - 2];

                       cache[1][i] = cache[1][i - 1] + cache[1][i - 2];

               }

               save = N;

        }

}

 

void initialize(void)

{

        memset(cache, 0, sizeof(cache));

        //피보나치수열을 위해서는 앞에 두개의 숫자가 필요하므로

        cache[0][0] = 1;

        cache[1][1] = 1;

}

 

int main(void)

{

        int T; //test_case

        cin >> T;

        initialize();

        for (int i = 0; i < T; i++)

        {

               cin >> N;

               if (N > 40 || N < 0)

                       exit(-1);

               fibonacci(N);

               cout << cache[0][N] << " " << cache[1][N] << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~