[백준 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)

이다.

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

 

입력

입력의 첫번째 줄을 테스트케이스의 개수 t (0 < t < 69)가 주어진다. 다음 t줄에는 몇번째 피보나치를 구해야하는지를 나타내는 n(0 ≤ n ≤ 67)이 주어진다.

출력

각 테스트케이스에 대해, 각 줄에 꿍 피보나치값을 출력하라.

예제 입력 1 

8
0
1
2
3
4
5
30
67

예제 출력 1 

1
1
2
4
8
15
201061985
7057305768232953720

이 문제를 틀렸다면 이유는 알고리즘적 문제가 아니라 자료형 선언일 것이다. 아마 int형으로 선언하지 않았을까 한다. DP문제로 메모리제이션 기법을 사용하여 풀이 하였다.

문제 난이도가 쉬우므로 자세한 설명은 생략하기로 한다. 피보나치 형식대로 함수를 구현해 주면 된다.

소스코드

// //  main.cpp //  DP // //  Created by seungwoo on 2018. 06. 28 //  Copyright © 2018년 seungwoo. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; long long fibo(int n); int main() { int T,n; cin>>T; while(T>0) { T--; cin>>n; cout<<fibo(n)<<endl; } return 0; } long long fibo(int n) { static long long dp[68]={0}; if(dp[n]!=0) return dp[n]; if(n==0 || n==1) return 1; else if(n==2) return 2; else if(n==3) return 4; return dp[n]=fibo(n-1) + fibo(n-2) + fibo(n-3) + fibo(n-4); }