[백준] 1563번. 개근상(JAVA)

문제

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

---

풀이(36분)

import java.io.*;

public class Main {
    static int n;
    static final int MOD = 1_000_000;

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

        int[][][] dp = new int[n + 1][2][3]; // [날짜][지각 횟수][연속 결석 횟수]

        dp[0][0][0] = 1; // 아무 기록이 없는 상태

        for (int day = 1; day <= n; day++) {
            for (int late = 0; late < 2; late++) { // 지각 0번 or 1번만 가능
                for (int absent = 0; absent < 3; absent++) { // 연속 결석 0~2번 가능
                    // 1. 출석 (지각 횟수와 연속 결석 초기화)
                    dp[day][late][0] = (dp[day][late][0] + dp[day - 1][late][absent]) % MOD;

                    // 2. 지각 (지각 횟수를 증가, 연속 결석 초기화)
                    if (late == 0) {
                        dp[day][1][0] = (dp[day][1][0] + dp[day - 1][late][absent]) % MOD;
                    }

                    // 3. 결석 (연속 결석 증가)
                    if (absent < 2) {
                        dp[day][late][absent + 1] = (dp[day][late][absent + 1] + dp[day - 1][late][absent]) % MOD;
                    }
                }
            }
        }

        int answer = 0;
        for (int late = 0; late < 2; late++) {
            for (int absent = 0; absent < 3; absent++) {
                answer = (answer + dp[n][late][absent]) % MOD;
            }
        }

        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

3중 포문을 사용하여 날짜당 지각, 결석의 개수를 반복해 주는 방법이다.

 

3중 포문을 사용했기에 반복이 매우 많을 수도 있지만 n = 1000이라는 범위 안에서 생각보다 가능한 반복이라 진행했다.

dp를 통해 3차원 배열을 만들어본 경험이 있다면 그다지 어렵지 않은 문제라고 생각한다.

 

dp를 도입한 근거는 다음과 같다.

이 문제에서 중요한 것은 지각을 배제할 수 있다는 것이다.

무슨 말이냐면 지각을 제외한 채로 결석과 출석만으로 문자열을 만든다.

예를 들면, 문제에서 제시된 4의 경우 L을 전혀 사용하지 않고 만드는 경우의 개수에 대해 구한다.

 

L을 전혀 사용하지 않는 경우에 대해 구할 때 길이를 N, N-1 두 개를 구한다.

그리고 N-1의 출석부에는 한 자리에 L이 들어가도 된다는 것을 통해 구한다.

그 외에 AALA같은 것도 구해야 한다.

하지만 이렇게 해도 dfs등에서 너무 많은 반복이 이루어질 수 있기 때문에 dp를 도입했다.

 

추가적으로 AALA같은 것을 구하기 어렵기에, 사용하지 않았다.