[C/C++] 백준 #1563 개근상(동적계획법)

개근상 문제는 동적계획법을 이용하는 문제이지만, 조건이 조금 까다롭습니다.  연속결석이 3번 이어지면 안 되기 때문에 당연히 동적 계획법을 사용하는 것이 바람직합니다.  그런데 지각 정보도 있으니까요.

 

출석은 O, 결석은 A, 지각은 L로 표현했을 때, 5일간 출석 정보를 가지고 개근상을 따진다면, 

OOOOO와 같은 경우는 당연히 되겠죠.  AALAL 과 같이 지각을 두번 이상한 경우에는 개근상을 받지 못합니다.  AALAA와 같이 4번 결석에 1번 지각의 경우는 개근상을 받겠죠.

 

개근상

 

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

1563번: 개근상

 

전 이 문제를 풀기 위해서 6가지 개근상을 받을 수 있는 상태를 정의했습니다.

상태	연속 결석수	지각수
0	0	0
1	1	0
2	2	0
3	0	1
4	1	1
5	2	1

이렇게 상태를 정의하면, 각 상태별로 갈 수 있는 전이 그래프가 생깁니다.

상태	출석(O)	결석(A)	지각(L)
0	0	1	3
1	0	2	3
2	0	-	3
3	3	4	-
4	3	5	-
5	3	-	-

이 전이 그래프에서 -는 갈 수 없는 곳입니다.  이것을 이용하면, 동적계획법 식을 만들 수 있습니다.  예를 들어서 \(d_{n, 1}\)의 상태는 다음과 같이 표현할 수 있습니다.

 

\[ d_{n, 1} = d_{n-1, 0}(input == A) \]

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------------------------------------
//    baekjoon #1563 - Prize strings
//        - by Aubrey Choi
//        - created at 2019-11-30
//------------------------------------------------------------------------------
#include <stdio.h>
#define MOD 1000000

//    Index    State        Can Next
//    0        0A, 0L        0, 1, 3
//    1        1A    0L        0, 2, 3
//    2        2A    0L        0, 3
//    3        0A    1L        3, 4
//    4        1A    1L        3, 5
//    5        2A    1L        3
int main()
{
    const int next[6][3] = { 0,1,3, 0,2,3, 0,3,-1, 3,4,-1, 3,5,-1, 3,-1,-1 };
    static long long dn[6][1001]; int n;
    scanf("%d",&n);
    dn[0][0] = 1;
    for( int i = 0; i < n; i++)
    {
        for( int j = 0 ; j < 6 ; j++ )
        {
            long long c = dn[j][i];
            for( int k = 0 ; k < 3 && next[j][k] != -1 ; k++ )
                dn[next[j][k]][i+1] = (dn[next[j][k]][i+1]+c)%MOD;
        }
    }
    long long ans = 0;
    for( int i = 0 ; i < 6 ; i++ ) ans += dn[i][n];
    printf("%lld\n", ans%MOD);
}