[자바로 푸는 백준] 1563번 개근상

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

1563번: 개근상

✅ 골드 Ⅳ

 

🔶 풀이

dp[날짜][지각 횟수][연속으로 결석한 횟수] 를 기준으로 dp 배열을 생성했다.

 

개근상을 받을 수 있는 조건은 총 6가지다.

 

1. 0번 지각, 0번 연속 결석 → dp[N][0][0]

2. 0번 지각, 1번 연속 결석 → dp[N][0][1]

3. 0번 지각, 2번 연속 결석 → dp[N][0][2]

4. 1번 지각, 0번 연속 결석 → dp[N][1][0]

5. 1번 지각, 1번 연속 결석 → dp[N][1][1]

6. 1번 지각, 2번 연속 결석 → dp[N][1][2]

 

1번부터 6번까지 차례대로 살펴보겠다.

 

1. N번째 날에 출석했을 경우, 0번 지각 0번 연속 결석은 전날에 출석하거나 결석 1번, 2번한 경우다.

dp[N][0][0] = dp[N-1][0][0] + dp[N-1][0][1] + dp[N-1][0][2]

 

2. 0번 지각 1번 연속 결석은 전날에 무조건 출석한 경우다.

dp[N][0][1] = dp[N-1][0][0]

 

3. 0번 지각 2번 연속 결석은 전날에 무조건 결석한 경우다.

dp[N][0][2] = dp[N-1][0][1]

 

4. 1번 지각 0번 연속 결석은 전날에 지각 1번 혹은 결석 1번, 2번한 경우, 그리고 지각 1번과 결석 1번, 2번을 동시에 한 경우다.

dp[N][1][0] = dp[N-1][0][0] + dp[N-1][0][1] + dp[N-1][0][2] + dp[N-1][1][0] + dp[N-1][1][1] + dp[N-1][1][2]

 

5. 1번 지각 1번 연속 결석은 전날에 1번 지각한 경우다.

dp[N][1][1] = dp[N-1][1][0]

 

6. 1번 지각 2번 연속 결석은 전날에 지각 1번, 결석 1번한 경우다.

dp[N][1][2] = dp[N-1][1][1]

 

마지막으로 개근상을 받을 수 있는 6가지 조건을 모두 더하고 출력해주면 된다.

 

 

<최종코드>

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

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[][][] dp = new int[1001][2][3];
		
        dp[1][0][0] = 1; // 출석 1일, 0번 지각, 0번 연속 결석
        dp[1][1][0] = 1; // 출석 1일, 1번 지각, 0번 연속 결석
        dp[1][0][1] = 1; // 출석 1일, 0번 지각, 1번 연속 결석
		
        for (int i=2; i<=N; i++) {
            dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % 1000000;
            dp[i][0][1] = dp[i-1][0][0] % 1000000;
            dp[i][0][2] = dp[i-1][0][1] % 1000000;
            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]) % 1000000;
            dp[i][1][1] = dp[i-1][1][0] % 1000000;
            dp[i][1][2] = dp[i-1][1][1] % 1000000;
        }
		
        System.out.println((dp[N][0][0] + dp[N][0][1] + dp[N][0][2] + dp[N][1][0] + dp[N][1][1] + dp[N][1][2]) % 1000000);
    }
}