[백준] S4 14495번 피보나치 비스무리한 수열 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14495번: 피보나치 비스무리한 수열

[문제] 

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

[입력]

자연수 n(1 ≤ n ≤ 116)이 주어진다.

[출력]

n번째 피보나치 비스무리한 수를 출력한다.

 

---

[풀이]

1. n을 입력받고 dp배열의 크기를 n으로 초기화해준다.

2. n은 1부터 입력이 되므로 그 위로의 값을 각 값의 크기에 맞춰서 배열을 채워준다.

3. 4 이상인 경우에는 점화식을 사용해 배열을 채워나가 준다.

4. 결과를 출력한다.

[접근]

1. 피보나치와 같지만 점화식만 조금 수정하면 되겠다고 생각하였다.

[코드]

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long[] dp = new long[n];
		
		dp[0] = 1;
		
		if (n >= 2)
			dp[1] = 1;
		if (n >= 3)
			dp[2] = 1;
		if (n >= 4) {
			for (int i = 3; i < n ; i++) {
				dp[i] = dp[i - 3] + dp[i - 1];
			}
		}
		
		System.out.println(dp[n - 1]);
	}
}