[자바] 백준 14495 - 피보나치 비스무리한 수열 (java)

 문제 : boj14495

---

 

필요 알고리즘 개념

• 동적 계획법 (DP; Dynamic Programming)
  • 일단 DP 문제긴 한데.. 사실 점화식이 이미 주어져 있어서 그냥 이전값을 활용하는 Memoization 수준의 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  식을 풀어나가다 보면 f(10) = f(9) + f(7) = f(8) + f(6) + f(6) + f(4) = f(7) + f(5) + f(5) + f(3) + f(5) + f(3) + f(3) + f(1) = ...

처럼 중복된 f(x)가 계속해서 등장하게 되는데, 그 때 마다 새로 계산해주면 매우 비효율적이므로 메모리에 담아두고 이미 계산된 것이라면 그걸 사용해주면 된다.

 

  그래서 DP문제긴 한데.. DP의 꽃(?)은 직접 점화식을 만드는데 있는데, 이미 점화식을 보여줬다!

그러니 그냥 n+1 크기의 배열을 만든 뒤, 기본값인 arr[1], arr[2], arr[3]을 1로 초기화 해주고 4부터 n까지 문제에서 제시된 점화식을 수행해주면 된다.

  

 

---

 

코드 : github

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

public class Main {
    private final static int LIMIT = 116;

    private long[] getFiboLikeSomething() {
        long[] arr = new long[LIMIT+1];
        arr[1] = arr[2] = arr[3] = 1;
        for (int i = 4; i <= LIMIT; i++) {
            arr[i] = arr[i-1] + arr[i-3];
        }
        return arr;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(getFiboLikeSomething()[n]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}