[백준] 1563 - 개근상(Java)

문제 파악

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

풀이

지각을 두 번 이상 했거나, 결석을 세 번 연속으로 하면 안 된다.
다시 말하면 지각은 모든 일정에서 1번까지만 허용되고, 결석은 연속으로 2회까지만 허용되는 것이다.

허용되는 출결 상태는 6개로 나눌 수 있다.

1. 지각 총 0회, 결석 누적 0회
2. 지각 총 0회, 결석 누적 1회
3. 지각 총 0회, 결석 누적 2회
4. 지각 총 1회, 결석 누적 0회
5. 지각 총 1회, 결석 누적 1회
6. 지각 총 1회, 결석 누적 2회

그렇다면 이전 날의 상태에 출석 / 지각 / 결석 을 수행하면 현재 날까지의 출결 상태를 결정할 수 있겠다.

1. 지각 총 0회, 결석 누적 0회
   • [지각 총 0회, 결석 누적 0회] (1) + 출석
   • [지각 총 0회, 결석 누적 1회] (2) + 출석
   • [지각 총 0회, 결석 누적 2회] (3) + 출석
2. 지각 총 0회, 결석 누적 1회
   • [지각 총 0회, 결석 누적 0회] (1) + 결석
3. 지각 총 0회, 결석 누적 2회
   • [지각 총 0회, 결석 누적 1회] (2) + 결석
4. 지각 총 1회, 결석 누적 0회
   • [지각 총 0회, 결석 누적 0회] (1) + 지각
   • [지각 총 0회, 결석 누적 1회] (2) + 지각
   • [지각 총 0회, 결석 누적 2회] (3) + 지각
   • [지각 총 1회, 결석 누적 0회] (4) + 출석 (이 부분을 놓쳐서 좀 헤맸다 🙃)
   • [지각 총 0회, 결석 누적 1회] (5) + 지각
   • [지각 총 0회, 결석 누적 2회] (6) + 지각
5. 지각 총 1회, 결석 누적 1회
   • [지각 총 1회, 결석 누적 0회] (4) + 결석
6. 지각 총 1회, 결석 누적 2회
   • [지각 총 1회, 결석 누적 1회] (5) + 결석

이를 3차원 DP 배열로 나타내 말일까지 전이하도록 하자.

배열에서 1차원은 날짜, 2차원은 총 지각 횟수, 3차원은 누적 결석 횟수로 설정하였다.
참고로 초기값(DP[0][0][0])은 1로 설정해주도록 한다.

코드

import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int day = sc.nextInt();
        sc.close();
        long[][][] dp = new long[day + 1][2][3];
        dp[0][0][0] = 1;
        for (int i = 1; i <= day; i++) {
            // 지각 0
            dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD;
            dp[i][0][1] = dp[i - 1][0][0]; // 결석 1
            dp[i][0][2] = dp[i - 1][0][1]; // 결석 2

            // 지각 1
            dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD;
            dp[i][1][1] = dp[i - 1][1][0]; // 지각 1 + 결석 1
            dp[i][1][2] = dp[i - 1][1][1]; // 지각 1 + 결석 2
        }

        long answer = 0;
        for (long[] d : dp[day]) {
            for (long val : d) {
                answer = (answer + val) % MOD;
            }
        }
        System.out.println(answer);
    }
}