[Algorithm] 백준 15990 - 1,2,3 더하기 5 (JAVA)

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

• 같은 수가 연속으로 나오면 안되므로 2차원 배열(n값, 마지막에 더해진 숫자)을 사용해서 분리 시켜 준다. dp[4]의 경우를 예시로 보자.
  dp[4] [1] : 즉 마지막에 1을 더해서 4를 만들 경우는 dp[3]이 2 또는 3을 더해서 나온 결과여야한다.
  이를 점화식으로 표현하면 다음과 같다.

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

• dp[1], dp[2] 는 자기 자신만 존재하므로 dp[1] [1] = 1, dp[2] [2] =1
  dp[3]은 1+2, 2+1, 3 이 존재하므로 dp[3] [1], dp[3] [2], dp[3] [3] = 1 이 점화식의 시작이 된다.

코드

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

public class Main {
    static final int DIV = 1_000_000_009;
    static long[][] dp = new long[100001][4];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        chkArray();
        int num = Integer.parseInt(br.readLine());
        while (num-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(chk(n)).append("\n");
        }
        System.out.println(sb);
    }

    private static long chk(int n) {
        return (dp[n][1] + dp[n][2] + dp[n][3]) % DIV;
    }

    private static void chkArray() {
        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = dp[3][2] = dp[3][3] = 1;
        for (int i=4; i<dp.length; i++) {
            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % DIV;
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % DIV;
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % DIV;
        }
    }
}