백준 1563 개근상

문제보기

실제로 이 문제를 푸는 방법은 여러가지가 있더라 , 

하지만 배열을 다루는 것에 있어 미숙한점을 알고 있기때문에

조건을 배열로 바꾸어 5차원 배열로 풀어보았다. 

 

풀이는 간단하지만 복잡하다. 

경우를 충분히 나누면 풀 수 있다. 

다만 그 경우가 다른 쉬운 다이나믹 문제보다 조건이 많아 처음에는

힘들었다. 

조건의 예를 들어보자 

점화식을 설명해보자면 

D[현재몇일][오늘의 출결][어제의 출결][그제의 출결][지각횟수]

이다. 

오늘 출결했다고 하면 뭘해도 상관없다.  이런식으로 조건을 나열하여 풀면된다. 

처음에는 상당히 시간이 걸렸다.

D[i][0][prev][prev2][0] += D[i-1][prev][prev2][prev3][0];

D[i][0][prev][prev2][1] += D[i-1][prev][prev2][prev3][1];

그리고 안되는 조건을 살펴보자면 

now , prev , prev2가 다 결석이면 안된다. 연속3일 결석을 할 수 가 없다. 

지각은 한번까지 허용된다. 그럼으로 오늘지각을 했다면 어제까지 지각을 하면안된다. 

주석을 달아놨으니 참고하면된다.

package Problems;
 
/**
 * 
 * 
 * 백준 1563 개근상
 * 
 * 동적계획
 *
 */
import java.util.Scanner;
 
public class boj1563dp {
    public static int mod = 1000000;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][][][][] D = new int[1001][3][3][3][2];
 
        for (int now = 0; now < 3; now++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
 
                    // 결석 연속3번은 안
                    if (now == 1 && prev == 1 && prev2 == 1) {
                        continue;
                    }
 
                    // 지각 2번은 안됨
                    if ((now == 2 && prev == 2) || (now == 2 && prev2 == 2) || (prev == 2 && prev2 == 2)) {
                        continue;
                    }
 
                    if (now == 2 || prev == 2 || prev2 == 2) {
                        D[3][now][prev][prev2][1] = 1;
                    } else {
 
                        D[3][now][prev][prev2][0] = 1;
 
                    }
 
                }
            }
        }
 
        for (int i = 4; i <= n; i++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
                    for (int prev3 = 0; prev3 < 3; prev3++) {
 
                        // 출석했을
                        D[i][0][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                        D[i][0][prev][prev2][0] %= mod;
                        D[i][0][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                        D[i][0][prev][prev2][1] %= mod;
 
                        // 결석
 
                        if (prev == 1 && prev2 == 1) {
 
                        } else {
 
                            D[i][1][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                            D[i][1][prev][prev2][0] %= mod;
                            D[i][1][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                            D[i][1][prev][prev2][1] %= mod;
 
                        }
 
                        D[i][2][prev][prev2][1] += D[i - 1][prev][prev2][prev3][0];
                        D[i][2][prev][prev2][1] %= mod;
 
                    }
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 2; l++) {
                        ans += D[n][i][j][k][l];
                        ans%=mod;
                    }
                }
            }
        }
        
        System.out.println(ans);
 
    }
 
}