백준 15990번 1, 2, 3 더하기 5 [ Java ]

15990번: 1, 2, 3 더하기 5

 

D[n]에 이전 수를 기억하는 변수를 두어 점화식을 세웁니다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        long mod = 1000000009L;
        long[][] D = new long[100001][4];
        for (int i = 1; i <= 100000; i++) {
            if (i-1 >= 0) {
                D[i][1] = D[i - 1][2] + D[i - 1][3];
                if (i == 1) D[i][1] = 1;
            }
            if (i-2 >= 0) {
                D[i][2] = D[i - 2][1] + D[i - 2][3];
                if (i == 2) D[i][2] = 1;
            }
            if (i-3 >= 0) {
                D[i][3] = D[i - 3][1] + D[i - 3][2];
                if (i == 3) D[i][3] = 1;
            }
            D[i][1] %= mod;
            D[i][2] %= mod;
            D[i][3] %= mod;
        }

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append((D[n][1] + D[n][2] + D[n][3]) % mod + "\n");
        }
        System.out.print(sb);
    }
}