[99클럽 코테 스터디 2일차 TIL] 피보나치 비스무리한 수열

 

2일차 문제

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

 

 

 

문제 풀이

주어진 계산식을 이용해 반복문, DP를 사용해 풀이

DP 공식은 이미 문제에서 주어졌으므로 어렵지 않았으나 주의해야 할 점은 arr[60]만 가도 이미 int의 범위를 초과해버리기 때문에 DP 배열인 arr을 long으로 선언해주어야 한다는 것이다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long[] arr = new long[N+1];
        
        if (N <= 3) {
            System.out.println(1);
            return;
        }

        // 초기 값 세팅
        for(int i=1; i<=3; i++) {
            arr[i] = 1;
        }

        // 공식 : f(n) = f(n-1) + f(n-3)
        for(int i=4; i<=N; i++) {
            arr[i] = arr[i-1] + arr[i-3];
        }
        System.out.println(arr[N]);
    }
}