[백준] 9507번 : Generations of Tribbles – JAVA [자바]

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

9507번: Generations of Tribbles

 

---

• 문제

 

---

• 문제 풀이

백준 9507번 Generation of Tribbles는 1차원 배열을 이용한 DP 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

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

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

 

이 문제는 피보나치 수열과 거의 유사한 DP 문제이다. 일반적인 피보나치 수열은 다음과 같다.

dp[n] = dp[n-1] + dp[n-2];

 

하지만 꿍만의 피보나치 수열은 다음과 같다.

dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] + dp[n-4];

 

---

• 코드

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 t = Integer.parseInt(br.readLine());
        long[] dp = new long[68];
        StringBuilder sb = new StringBuilder();
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i<= 67; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4];
        }
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n] + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

되게 간단한 피보나치를 응용해서 푸는 실버 3 난이도의 DP 문제였던 거 같다.