[Algorithm]Baekjoon 1563번 :: 개근상

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

1563번: 개근상

 
int n;
int dp[1001][2][3] = { 0 };
const int mod = 1000000;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    dp[1][0][0] = dp[1][0][1] = dp[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]) % mod; // 1,2번 연속결석하더라도 출석하면 다시 초기화.
        dp[i][0][1] = dp[i - 1][0][0] % mod;
        dp[i][0][2] = dp[i - 1][0][1] % mod;
        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]) % mod;
        dp[i][1][1] = dp[i - 1][1][0] % mod;
        dp[i][1][2] = dp[i - 1][1][1] % mod;
    }
 
 
    cout << (dp[n][0][0] + dp[n][0][1] + dp[n][0][2] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]) % mod;
}

 

 

전형적인 DP문제로써, 풀어보는걸 추천한다. 

이 문제는 생각보다 쉽지 않다. 이전에 비슷한 유형을 풀어본사람이라면 모를까, 그런게 아니라면 쉽지 않을것이다.

 

일단 개근상을 받을 수 있는 조건을 따져본다. N번째 날까지 지각은 2번 이상이면 안되고, 결석은 '연속'으로 3번 이상이면 안된다. 여기서 결석은 '연속'이란걸 명심해야한다. 지각은 계속 누적되지만, 결석은 1,2번 연속결석하더라도 그다음에 '출석'이나 '지각'을 하면 다시 0으로 카운팅이 초기화된다.

 

그렇다면 DP테이블을 아래와같이 잡아보자.

 

dp[n][2][3]

 

dp[n][0][0]은 n번째날에 지각 0번,결석 0번한 학생수를 의미한다.

dp[n][0][1]은 n번째날에 지각 0번, 결석 연속으로 1번한 학생수를 의미한다. 이런 의미의 dp테이블이다.

 

자 그러면 dp[n][0][0]에는 어떤값이 들어가야할까?

일단 dp[n-1][0][0], 즉 전날의 지각 0번,결석 0번한 학생수가 들어가야한다.(여기까지는 쉽게 알 수 있을것이다)

거기에 더해 dp[n-1][0][1]도 들어갈 수 있다..! 그리고 dp[n-1][0][2]도 마찬가지.

[0][1]이나 [0][2]나 같은 메커니즘이니 [0][1]을 예시로 설명해보겠다.

 

일단 [n-1][0][1]은 전날 1번 결석한 사람의 수이다. 이 상태에서 n번째날에 출석을 했다고 가정해보자.

결석은 '연속'해야하기 때문에 한번이라도 출석or지각을 한다면 그냥 0이 된다고 앞서 말했다.

그렇기때문에 [n][0][0]에 [n-1][0][1]과 [n-1][0][2]값이 들어갈 수 있다는 것이다.

전날에 결석 한번을 했든, 연속 두번을했든 n번째날에 출석해버리면 0으로초기화되기 때문이다.

 

[n][0][1]과 [n][0][2]는 경우의수가 한가지씩밖에없다. 결석은 연속해야하기 때문이다.

그래서 [n][0][1] = [n-1][0][0] 이고 [n][0][2] = [n-1][0][1]이다.

 

그다음 dp[n][1][0]을 보자. 들어가야할 값이 제일 많다. 

 

dp[n-1][0][0] // 전날 0번지각, 0번결석한 상태에서 n번째날에 '지각'하면 dp[n][1][0]이 충족된다.

dp[n-1][0][1] // 전날 0번지각, 1번결석한 상태에서 n번째날에 '지각'하면 dp[n][1][0]이 충족된다.

                        지각한 순간, 연속결석카운팅은 0으로 초기화되기 때문이다.

dp[n-1][0][2] // [0][1]과 동일하다.

 

dp[n-1][1][0] // 전날 1번지각, 0번결석한 상태에서 n번쨰날에 그냥 '출석'하면 dp[n][1][0]이 충족된다.

dp[n-1][1][1] // 전날 1번지각, 1번결석한 상태에서 n번째날에 그냥 '출석'하면 dp[n][1][0]이 충족된다.

                        이유는 [0][1]과 동일하다. 출석하면 연속결석카운팅은 0으로 초기화되기 때문이다.

dp[n-1][1][2] // 이하동문.

 

 

dp[n][1][1]과 dp[n][1][2]는 [0][1]과 [0][2]의 이유와 똑같다.