백준 1563 개근상 python, java

결석은 연속해서만 안하면 되지만 지각은 2번만하면 바로 개근상 컷당하는 이상한 학교..
N이 1000이기때문에 모든 경우의 수를 구할 순 없었고 DP로 접근해야되는 문제임을 알았다.

📜 문제 바로 가기 : 개근상

제출코드

python

import sys
input = sys.stdin.readline

N = int(input())

DP_0 = [[0] * 4 for _ in range(N)]  # 지각 0번
DP_1 = [[0] * 3 for _ in range(N)]  # 지각 1번

# 출석, 결석1, 결석2, 지각
DP_0[0] = [1, 1, 0, 1]

k = 1000000
for i in range(1, N):
    DP_0[i][0] = (DP_0[i-1][0] + DP_0[i-1][1] + DP_0[i-1][2]) % k
    DP_0[i][1] = (DP_0[i-1][0]) % k
    DP_0[i][2] = (DP_0[i-1][1]) % k
    DP_0[i][3] = (DP_0[i-1][0] + DP_0[i-1][1] + DP_0[i-1][2]) % k

    DP_1[i][0] = (DP_0[i-1][3] + DP_1[i-1][0] + DP_1[i-1][1] + DP_1[i-1][2]) % k
    DP_1[i][1] = (DP_0[i-1][3] + DP_1[i-1][0]) % k
    DP_1[i][2] = (DP_1[i-1][1]) % k

print((sum(DP_0[N-1]) + sum(DP_1[N-1])) % k)

자바

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[][] one = new int[n][4];
        int[][] two = new int[n][3];

        int k = 1000000;

        one[0] = new int[]{1, 1, 0, 1};

        for (int i = 1; i < n; i++) {
            one[i][0] = (one[i-1][0] + one[i-1][1] + one[i-1][2]) % k;
            one[i][1] = (one[i-1][0]) % k;
            one[i][2] = (one[i-1][1]) % k;
            one[i][3] = (one[i-1][0] + one[i-1][1] + one[i-1][2]) % k;

            two[i][0] = (one[i-1][3] + two[i-1][0] + two[i-1][1] + two[i-1][2]) % k;
            two[i][1] = (one[i-1][3] + two[i-1][0]) % k;
            two[i][2] = (two[i-1][1]) % k;
        }

        int ans = (Arrays.stream(one[n-1]).sum() + Arrays.stream(two[n-1]).sum()) % k;
        System.out.println(ans);

    }

}

---

접근방법

지각이 누적되기 때문에 지각했다는 것을 알 수 있는 방법이 필요했다.
나는 그냥 지각을 한 번도 안 한 DP_0배열과 지각을 1번한 DP_1배열로 나눠서 생각했다.

DP_0배열은 i행의 크기가 4인 2차원배열이다. 각 값은 차례대로 i일수에서 출석, 결석, 결석연속 2번, 지각한 날의 경우의 수를 가진다.
DP_1배열은 DP_0배열에서 지각만 뺀 크기 3의 2차원배열이다. 지각 2번은 개근상을 못받기 때문!

초기값

DP_1배열의 초기값은 모두 0이다. 왜냐하면 DP_1자체가 지각을 1번 했다는 전제로 가는데
지각을 1번 하기 위해서는 최소 둘째날부터 값을 쓸 수 있기 때문이다.

DP_0의 첫째날값은 결석2연을 제외하고 모두 가능함으로 [1, 1, 0, 1]로 둔다.