[백준] S3 9507번 Generations of Tribbles (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

9507번: Generations of Tribbles

[문제] 

꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 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. dp 배열을 만들어 초기값을 넣어준다.

2. dp 배열을 채워준다.

3. t만큼 반복을 돌며 결과를 출력한다.

[접근]

1. 피보나치와 같은 방식으로 주어진 식에 맞춰서 문제를 해결하면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, t;
	static long dp[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		
		dp = new long[70]; // 넉넉잡아 70개
		
		// 초기값 설정
		dp[0] = dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		// dp 배열 채우기
		for (int i = 4; i < 70; i++) {
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
		}
		
		// 해당 값 출력
		for (int T = 0; T < t; T++) {
			System.out.println(dp[Integer.parseInt(br.readLine())]);
		}
	}
}