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

-Code

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

public class BOJ15990 {
    // dp 셋팅
    static long[][] dp = new long[100001][3];
    static long MOD = 1000000009;
    static {
        dp[1][0] = 1;
        dp[2][1] = 1;
        dp[3][0] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        // dp의 상태를 끝나는 수 1 2 3으로 나눠서 계산
        for (int row = 4; row < 100001; row++) {
            // 해당 끝나는 숫자에 따라 -1, -2, -3 위치의
            // 같은 숫자가 아닌값 더함
            dp[row][0] = (dp[row - 1][1] + dp[row - 1][2]) % MOD;
            dp[row][1] = (dp[row - 2][0] + dp[row - 2][2]) % MOD;
            dp[row][2] = (dp[row - 3][0] + dp[row - 3][1]) % MOD;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = 
                new BufferedReader(new InputStreamReader(System.in));
        
        int testCase = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCase; i++) {
            int n = Integer.parseInt(br.readLine());

            long answer = 0;
            for (int col = 0; col < 3; col++) {
                answer = (answer + dp[n][col]) % MOD;
            }
            System.out.println(answer);
        }
    }
}

처음 보고 문제를 푸는데 이것도 익숙하지 않아서 2차원 배열을 생각하지 못했습니다. 그래서 1차원 배열로 이상한 로직을 짜게 되었고 틀렸습니다. 이후 힌트를 1개씩 받아 다음 날 다시 풀어보고 했는데 첫날은 각각 상태를 관리해야 한다고 하여 시작점을 기준으로 잡고 했으나 문제가 풀리지 않아서 마지막 숫자를 기준으로 잡고 하라와 그 값이 -1, -2, -3을 비교해야 한다라는 힌트를 다시 받았습니다. 그 결과 해결했으나 익숙하지 않아서 점화식을 세우는 게 어려워서 dp문제를 더 많이 풀어봐야겠다고 생각했습니다.