백준 9507 Generations of Tribbles

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

'프로그래밍 대회에서 배우는 알고리즘 문제해결전략'에서 배운 메모이제이션 기법을 사용하여 쉽게 풀 수 있었습니다.

주어진 조건대로 재귀함수를 작성하면 됩니다!

/*

꿍은 군대에서 진짜 할짓이 없다.그래서 꿍만의 피보나치를 만들어보려고 한다.기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다.그래서 다음과 같은 피보나치를 만들었다.꿍만의 피보나치 함수가 koong(n)이라고 할 때,

n < 2 : 1

n = 2 : 2

n = 3 : 4

n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)

이다.

여러분도 꿍 피보나치를 구해보아라.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 67;

 

int N;

long long cache[MAX + 1];

 

long long koong(int num)

{

        //메모이제이션

        long long &result = cache[num];

        if (result != -1)

               return result;

        //주어진 조건

        if (num < 2)

               return result = 1;

        if (num == 2)

               return result = 2;

        if (num == 3)

               return result = 4;

        return result = koong(num - 1) + koong(num - 2) + koong(num - 3) + koong(num - 4);

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>69)

               exit(-1);

 

        memset(cache, -1, sizeof(cache));

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

        {

               cin >> N;

               if (N < 0 || N > MAX)

                       exit(-1);

               cout << koong(N) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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