[백준 1563번] 개근상 (C++)

문제링크 : https://www.acmicpc.net/problem/1563

1563번: 개근상

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 
const int MOD = 1000000;

int N;
int dp[1001][2][3]; //날짜, 지각, 결석

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 1; //출석, 지각 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]) % MOD; //0번 지각, 0번 결석
        dp[i][0][1] = dp[i-1][0][0] % MOD; //1번 결석
        dp[i][0][2] = dp[i-1][0][1] % MOD; //2번 결석
        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; //1번 지각
        dp[i][1][1] = dp[i-1][1][0] % MOD; //1번 지각, 1번 결석
        dp[i][1][2] = dp[i-1][1][1] % MOD; //1번 지각, 2번 결석
    }

    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;
    return 0;
}

 

우선 출결정보가 무사히 담기는 경우가 다음과 같이 6가지가 있다.

1. 지각도 결석도 안한 경우
2. 1번 결석하는 경우
3. 2번 연속 결석하는 경우
4. 1번 지각하는 경우
5. 1번 지각, 1번 결석하는 경우
6. 1번 지각, 2번 연속 지각하는 경우

 

위 각 케이스에  대해 그 전에 어떠한 값들이 올 수 있는 지를 확인하고 해당 값들을 더해준다.

먼저 초기화의 경우 첫째날에 해당한다.

첫째날은 지각도 결석도 안한 경우 / 지각 1번 한 경우 / 결석 1번 한 경우가 가능하며 첫째날이기에 1로 초기화해준다.

 

1. 지각도 결석도 안한 경우

직전 값으로는 똑같이 지각도 결석도 안한 경우 / 1번 결석한 경우 / 2번 연속 결석한 경우가 올 수 있다.

위 3가지 경우 직전 값들을 더해준다.

 

2. 1번 결석하는 경우

직전으로 결석 0번인 경우만 오는 것이 가능하다.

 

3. 2번 연속 결석하는 경우

2번과 유사한 케이스로, 1번 결석한 경우만 오는 것이 가능하다.

 

4. 1번 지각하는 경우

올 수 있는 직전 케이스가 가장 많은 경우이다.

1번과 같이 우선 지각도 결석도 안한 경우 / 1번 결석한 경우 / 2번 연속 결석한 경우가 올 수 있다.

(지각도 출석과 마찬가지로 연속 결석이 깨지기 때문)

 

여기에 직전에 한번 지각한 경우 / 1번 지각 + 1번 결석한 경우 / 1번 지각 + 2번 연속 결석한 경우가 올 수 있다.

(현재 값은 1번 지각하고 출석한 상태)

 

5. 1번 지각, 1번 결석하는 경우

2번과 유사한 케이스로, 1번 지각하고 결석 0번인 오는 것이 가능하다.

 

6. 1번 지각, 2번 결석하는 경우

3번과 유사하한 케이스로, 1번 지각하고 1번 결석한 경우만 오는 것이 가능하다.

 

위를 토대로 주어진 N에 대한 6가지 케이스를 더한 값을 MOD로 나눈 나머지를 출력해주면 된다.