[JAVA] 백준 9507번 : Generations of Tribbles

 

---

 

• 생각

보자마자 피보나치 수열이 생각 났다. N이 3보다 클땐 해당 인덱스 -1,-2,-3,-4한 값들을 모두 더해주면 된다.

 

• 코드

정답 코드 : 피보나치와 비슷한 방식이다. 피보나치는 전 index, 전전 index인 2개 수를 더했다면 해당 문제는 전, 전전, 전전전, 전전전전 index의 값을 더 해주면 된다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[] array = new long[69];
        array[0] = 1;
        array[1] = 1;
        array[2] = 2;
        array[3] = 4;
        for(int i = 4; i < 68; i++)
            array[i] = array[i - 1] + array[i - 2] + array[i - 3] + array[i - 4];
        
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(array[n]);
        }
    }
}