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

난이도

실버 2

문제

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

풀이

이 문제는 9095번 1,2,3 더하기와 비슷하지만 조건이 하나 추가되었습니다.
같은 수를 두 번 이상 연속해서 사용하면 안된다는 조건입니다.

이 점을 고려하여 문제를 풀어보겠습니다.

1. 테이블 정의하기
   DP[n] = n을 만들기 위한 경우의 수

2. 점화식찾기
   1) 7을 만드는 수식 중 마지막이 1로 끝나는 것의 수
   7 = 6을 만드는 수식 중 마지막이 2로 끝나는 것 +1
   7 = 6을 만드는 수식 중 마지막이 2로 끝나는 것 +1
   DP[7][1] = DP[6][2] + DP[6][3]

2) 7을 만드는 수식 중 마지막이 2로 끝나는 것의 수
7 = 5을 만드는 수식 중 마지막이 1로 끝나는 것 +2
7 = 5을 만드는 수식 중 마지막이 3로 끝나는 것 +2
DP[7][2] = DP[5][1] + DP[5][3]

3) 7을 만드는 수식 중 마지막이 3로 끝나는 것의 수
7 = 4를 만드는 수식 중 마지막이 1로 끝나는 것 +3
7 = 4를 만드는 수식 중 마지막이 2로 끝나는 것 +3
DP[7][3] = DP[4][1] + DP[4][2]

따라서 점화식은
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]

3. 초기값 정의하기
   dp[1][1] = 1
   dp[2][2] = 1
   dp[3][1] = 1
   dp[3][2] = 1
   dp[3][3] = 1

코드

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

// 15990번 1, 2, 3 더하기 5
public class boj_7_15990 {
    static long[][] dp = new long[100001][4];
    static final int MOD = 1000000009;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;


        for (int i = 4; i <= 100000; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
        }


        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            long result = (dp[n][1] + dp[n][2] + dp[n][3]) % MOD;
            sb.append(result).append("\n");
        }
        System.out.println(sb);


    }
}