백준 1563. 개근상

문제 바로가기

개근상

문제 요약

출석, 지각, 결석이 기록되는 백준중학교에서 지각을 두 번 이상 했거나 결석을 연속으로 세 번 한 사람은 개근상을 받을 수 없다. N일이 주어졌을 때, 개근상을 받을 수 있는 경우의 수를 세는 프로그램을 작성하시오.

문제 풀이 포인트

결석보다 지각이 더 허용이 되지 않는 학교로 굉장히 이상한 학교다. 결석을 연속 2번씩 하고 3일에 한 번씩만 학교나가면 되는 학교.. 문제로 돌아와서 주어지는 N에 비해 걸리는 시간이 굉장히 부족하기 때문에 이 문제는 dp방식으로 접근해야한다.

먼저 i번째 날에 출석을 하는 경우, 결석하는 경우, 지각하는 경우 세가지로 나누어 생각할 수 있다. 세가지를 담아야 하기 때문에 dp 배열은 3차원으로 생각해야 하고 지각은 2번, 결석은 3번까지 가능하기 때문에 DP[날짜][지각 횟수][연속으로 결석한 수]로 생각하여 dp[N+1][2][3] 으로 초기화할 수 있다.

개근상이 가능한 경우를 모두 만들어보면

1. 지금까지 지각을 한번도 안한 경우

• i번째 날에 출석을 하게 되면

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

  이때, 결석을 i-1번째 날까지 2번 연달아 했더라도 출석을 하게 되면 초기화되기 떄문에 결석 수를 0번 인덱스에 담아야한다.

• i번째 날에 결석을 연속으로 한 번 했다면 i-1번째 날에는 결석을 하면 안되므로

  dp[i][0][1] = dp[i-1][0][0]

• i번째 날에 결석을 연속으로 두 번 했다면 i-1번째 날에는 결석을 한번 해야 하므로

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

1. 지금까지 지각을 한번 한 경우

• i번째 날에 출석을 하게 되면 이미 이전에 한번 결석을 한번 했으므로

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

• i번째 날에 지각을 하게 되면 i-1번째 날까지는 지각을 한번도 하지 않았기 때문에 지각 0번 인덱스에서 뽑아와야한다.

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

• i번째 날에 결석을 연속으로 한번, 두번 한 경우인 dp[i][1][1]과 dp[i][1][2]는 dp[i][0][1], dp[i][0][2] 와 형태가 유사하다.

그래서 N번째 날의 개근상이 가능한 날은 dp[N]의 아래 차원 배열의 값을 모두 더하면 N번째 날의 개근상이 가능한 경우의 수가 나온다.

문제 코드[JAVA]

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        final int D = 1000000;
        int[][][] dp = new int[N+1][2][3];
        dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 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]) % D;
            dp[i][0][1] = dp[i-1][0][0] % D;
            dp[i][0][2] = dp[i-1][0][1] % D;
            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]) % D;
            dp[i][1][1] = dp[i-1][1][0];
            dp[i][1][2] = dp[i-1][1][1];
        }
        int ans = 0;
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) {
                ans += dp[N][i][j];
            }
        }
        System.out.println(ans % D);
        sc.close();
    }
}