[백준 알고리즘]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번째 피보나치 비스무리한 수를 출력한다.

 

[예제]

 

---

>문제 풀이

 

 

 예전에 틀렸던 문제가 몇 개 있길래 뭘 틀렸나 싶어서 다시 풀어보려고 한다.

오늘 문제는 쉬웠었는데, 아마 풀다가 말았던게 아닌가 싶다.

 

arr[1], arr[2], arr[3]=1 미리 넣어주고(단 입력값에 따라 대입 처리를 해줘야한다.)

arr[i]= arr[i-3]+arr[i-1]; 을 for문 돌려주면 된다.

 

 

>전체 코드

 

import java.util.*;

public class Main {
	
	public static void main(String [] args) {
		int N;
		long arr[];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		arr= new long[N+1];
		
		arr[1]=1;
		if(N>1) arr[2]=1;
		if(N>2) arr[3]=1;
		for(int i=4; i<=N; i++) {
			arr[i]=arr[i-3]+arr[i-1];
		}
		
		System.out.println(arr[N]);
        
    }//main	
}

https://www.acmicpc.net/problem/14495

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