문제
꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 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 |
더보기
Solution
#include<stdio.h>
long long int koongFibonacci[68]={0, };
long long int koong(int N)
{
if(koongFibonacci[N]!=0)
return koongFibonacci[N];
koongFibonacci[N]=koong(N-1)+koong(N-2)+koong(N-3)+koong(N-4);
return koongFibonacci[N];
}
int main(void)
{
int t, n;
koongFibonacci[0]=koongFibonacci[1]=1;
koongFibonacci[2]=2;
koongFibonacci[3]=4;
scanf("%d", &t);
for(int i=0;i<t;i++)
{
scanf("%d", &n);
printf("%lld\n", koong(n));
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 18247번: 겨울왕국 티켓 예매 (0) | 2020.08.03 |
---|---|
<백준 알고리즘> 13015번: 별 찍기 - 23 (0) | 2020.07.30 |
<백준 알고리즘> 10866번: 덱 (0) | 2020.07.26 |
<백준 알고리즘> 1237번: 정ㅋ벅ㅋ (0) | 2020.07.26 |
<백준 알고리즘> 19532번: 수학은 비대면강의입니다 (0) | 2020.07.26 |