99클럽 코테 스터디 2일자 TIL [04/01]

참여 난이도

자바/미들러

오늘의 문제

백준 14495 피보나치 비스무리한 수열

 

 

문제 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long[] arr = new long[116];
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 1;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 3; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 3];
        }
        System.out.println(arr[n - 1]);
        
        scanner.close();
    }
}

 

두 가지 방법이 생각났습니다.

 

1. DP

2. 재귀 + 메모이제이션

 

1번 방식으로 생각했고, 다음과 같은 방식으로 점화식이 세워집니다.

f(n) = f(n - 3) + f(n - 1)

 

주의해야할 점은 답의 범위였습니다.

 

int형의 자료형 42만을 넘어서는 값이 나오기 때문에 long으로 선언해주었습니다.