[항해 99 클럽 6기/백준] Day 2 - 14495 피보나치 비스무리한 수열

[시간 제한] [메모리 제한]
 2 초          512 MB

[문제]
피보나치 비스무리한 수열은 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] 
10

[예제 출력 1] 
19

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    //자리수 이슈로 인해 long으로 선언해야 할 것
	static long[] arr;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(bf.readLine());
		arr = new long[117];
		
		arr[1] = 1;
		arr[2] = 1;
		arr[3] = 1;
		
		for(int i = 4 ; i < num+1 ; i++) {
			arr[i] = arr[i-1]+ arr[i-3];
		}
			
		System.out.println(arr[num]);
	}
	
}

 

 

** 가장 기본적인 dp문제인데, 오랜만에 풀다보니 자리수 문제를 주의하지 못했던거 같다.

  조심해야지