백준 9507(JAVA)

문제

문제에 주어진 꿍 피보나치를 통해서 주어진 입력에대한 답을 구하면된다.
꿍 피보나치는 d[n] = d[n - 1] + d[n - 2] + d[n - 3] + d[n - 4]이다.

풀이

귀여운 꿍문제를 어떻게풀까?
피보나치 문제기 때문에 dp테이블에 메모이제이션해나가며 풀면 시간초과가 나지않겠다.
바텀업으로 반복문으로 풀었당! (재귀함수로 풀어도됩니당!)
타입에 주의해야한다.

코드

package baekjoon.DP;

import java.io.*;

public class Main9507 {
    static int T;
    static long[] d = new long[70];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());
        dpSolve();
        for(int i = 0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(d[n] +"\n");
        }
        bw.flush();
        bw.close();
    }
    static void dpSolve(){
        d[0] = 1;
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
        for(int i = 4; i < 70; i++){
            d[i] = d[i - 1] + d[i - 2] + d[i - 3] + d[i - 4];
        }
    }
}