Boj 1563 c++ 개근상

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

 

 

3차원 dp 아이디어를 떠올리고 구현에 성공하였다. 기쁘다.

 

 

문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

 

 

접근

 

우선 조건을 보자마자 지각을 했느냐 하지 않았느냐의 여부가 중요할 것 같다는 생각이 들었다. 전체 학기 일 수에서 한개 이상으로 존재할 수 없기 때문이다. 그리고 결석여부의 '연속성' 조건에서는 3 x N 타일링 방식의 점화식을 짜야겠다는 생각이 들었다. 결석의 연속(스트릭)은 이전 출석 단계에서 얼마나 연속한 상태인지가 중요하기 때문이다.

ex) 현재 조건 = 3번 이상 연속으로 결석할 수 없다.

--> 이전 출석 단계에서 이틀 연속 결석한 상태 --> 반드시 다음날에는 지각, 또는 출석을 해야 한다.

 

이러한 조건 때문에 현재 몇번 연속으로 결석한 상태인지(3가지 경우)를 구분하는 조건도 있어야 겠다는 생각을 했다.

 

결국 'dp[N][i][j] = N일까지 출결 사항을 고려했을 때 현재 i일 연속 결석 상태이며, 지금까지 지각을 j번 했을 때의 경우의 수'

라고 dp배열을 정의하게 되었다.

 

 

풀이 

 

접근에서 생각한대로 점화식을 일일이 하나하나 다 짰다. 

조건분기가 까다로운 부분이 몇가지 존재했다.

 

'현재까지 지각하지 않았으며 결석 스트릭이 0인 경우' 는

이전 상태로 모든 경우를 취할 수 있다. 스트릭을 0으로 만들기 위해서는 이전 상태에 관계 없이 '출석'을 하면 되기 때문이다.

참고로 '지각을 하지 않아야 한다' 라는 전제가 있기 때문에 '출석'만이 가능한 것이다.

 dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]) % MOD;

 

반대로 '현재까지 지각을 한번 하였으며, 스트릭이 0인 경우' 는

위에서 구한 dp[i][0][0] 값을 이용하여야 한다. 이전 상태에서 이미 지각을 한 상태일 수도 있지만, 지금까지 지각을 하지 않았는데 이번에 지각을 하여 dp[N-1][0][0]에서 dp[N][0][1]이 된 경우도 고려할 수 있기 때문이다.

즉,  dp[i][0][0] 상태에서 출석이 아닌 지각으로 결석스트릭을 깬 경우이다.

 dp[i][0][1] = (dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1] + dp[i][0][0]) % MOD;

 

나머지 경우, 스트릭이 1일인 경우, 2일인 경우는 이전상태가 한정되어 고려할 것이 더 이상 없다.

 

 

전체코드

#include <iostream>
#define MOD 1000000
using namespace std;

int dp[1001][3][2]; /*

dp 배열 정의 : N일까지  결석을 연속 0번인 상태, 1번인 상태, 2번인 상태
3가지 구분
현재 까지 지각을 했는지의 여부를 판단하는 경우 2가지
*/

int main() {

    int N, ans = 0;

    cin >> N;

    dp[1][0][1] = 1; // L
    dp[1][1][0] = 1; // A
    dp[1][0][0] = 1; // O

    for(int i = 2; i <= N; i++) {
        dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]) % MOD;
        dp[i][1][0] = dp[i-1][0][0];
        dp[i][2][0] = dp[i-1][1][0];

        dp[i][0][1] = (dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1] + dp[i][0][0]) % MOD;
        dp[i][1][1] = dp[i-1][0][1];
        dp[i][2][1] = dp[i-1][1][1];

    }

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 2; j++) {
            ans = (ans + dp[N][i][j]) % MOD;
        }
    }
    cout << ans;
}

 

 

+

이번 문제로 300솔브를 달성했다.

 

앞으로도 열심히 하겠다.