[백준] 14495번 : 피보나치 비스무리한 수열 – JAVA [자바]

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

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

 

---

• 문제

 

---

• 문제 풀이

백준 14495번 피보나치 비스무리한 수열은 DP를 이용해서 푸는 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

백준 14495번 피보나치 비스무리한 수열은 피보나치 수열과 매우 흡사하다. 피보나치 수열은 f(n) = f(n-1) + f(n-2)인데 이번 문제에서 나온 수열은 f(n) = f(n-1) + f(n-3)이다. 

 

따라서 long형 배열 dp를 만든 후 loop을 돌려 dp [i] = dp [i-1] + dp [i-3]만 해주면 된다. 이 문제에서는 입력 n을 받는데 범위는 1 ≤ n ≤ 116이다. n = 116이면 int형의 범위를 넘어가기 때문에 꼭 long형 배열로 해줘야 한다.

 

예시를 한 번 보겠다.

 

---

• 코드

 

import java.util.*;
import java.io.*;
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[] dp = new long[117];
        dp[1] = dp[2] = dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-3];
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

이 문제는 이전에 많이 풀어봤던 피보나치 수열과 비슷해서 쉽게 풀 수 있는 문제였다.