백준) 1563 개근상

1563. 개근상

문제

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

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

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

한 학기가 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이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 

4

예제 출력 

43

1. 접근

하루에 할 수 있는 출결은 세 가지이다. 몇일 동안 출결할지 정해지고, 상을 탈 수 있는 조건이 주어졌을 때 조건을 만족하는 출결순열의 경우가 총 몇가지 인지 구해야 한다.

조건이 없다면 3 ^ N 가지의 경우가 있겠지만, 조건은 지각은 한번만 가능하고, 결석은 이틀까지만 연속으로 가능하다.

이틀 결석하고 출석하고, 이틀 결석하고 출석하는 경우가 가능하다는 뜻이다.

어떤 방법을 써야 모든 경우를 잘 셀 수 있을까?

2. 풀이

직관적으로 가능한 모든 조합을 확인하는 방법이 있겠다. 하지만 N은 최대 1000일 이므로, 3 ^ 1000 개의 조합을 확인하기엔 시간이 모자르다.

그러면 어떤 규칙을 통해 모든 조합을 확인하지 않아도 될까?

당장에 어떤 수학적인 규칙은 보이지 않으므로,

가능한 경우를 계속 늘려가면서 세버리는 다이나믹 프로그래밍을 쓰기로 하자.

그러면 조건을 잘 활용해야 한다. 지각의 횟수는 계속 누적되고, 결석은 누적되지 않는다는게 특징이다.

배열은 다음과 같이 정의한다.

DP[지금까지 출결한 날][지금까지 지각한 횟수][지금까지 연속으로 결석한 횟수] = DP[day][cnt1][cnt2]

= 지금까지 상황이 이러저러 할 때, 최종적으로 조건을 만족하는 경우의 수

당연히 문제의 답은 DP[0][0][0]에 있을 것이다.

N = 4 라면 DP[4][1][2] = 1이다. 반대로 DP[4][2][2] = 1이다.

DP배열을 갱신해줄 함수는 다음과 같다.

func(int day, int cnt1, int cnt2) = DP[day][cnt1][cnt2] 를 잘 계산해준다.

함수가 종료될 기저사례는 무엇이 있을까

우선 cnt1이 2까지 차버렸거나, cnt2가 3까지 차버린 경우다. 이러면 앞으로 무슨 출결을 해도 상을 못받는다

= return 0

우여곡절로 N일 까지 도착했다면, 앞의 기저사례는 통과했다는 뜻이니까 상을 받을 수 있다.

 = return 1

내일의 출결은 세가지 가능하다.

1. 잘 출결한다 -> func(day + 1, cnt1, 0) 지각은 누적제이고, 결석은 사라진다.

2. 지각한다 -> func(day + 1, cnt1 + 1, 0) 지각은 누적제이고, 결석은 사라진다.

3. 결석한다 -> func(day+1, cnt1, cnt2 + 1) 지각은 누적제이고, 결석을 연속으로 해버렸다.

함수는 잘 확장되고 기저사례에 알아서 도착해 값을 리턴해줄 것이다.

메모이제이션을 통해 중복계산을 줄일 수도 있다.

3. 코드

#include <stdio.h>
#include <string.h>
using namespace std;
 
int n;
int dp[1001][3][4];
 
int func(int day, int c1, int c2) {
    if (c1 >= 2 || c2 >= 3)
        return 0;
 
    if (day == n)
        return 1;
 
    int& ref = dp[day][c1][c2];
    if (ref != -1)
        return ref;
 
    return ref = 
        (func(day + 1, c1, 0) + 
        func(day + 1, c1 + 1, 0) + 
        func(day + 1, c1, c2 + 1)) % 1000000;
}
 
int main() {
    scanf("%d", &n);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0, 0));
 
    return 0;
}