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

 

1563번: 개근상

DP문제였다. 나는 Top-Down으로 풀었다. 인터넷에 Top-Down으로 푼 사람이 별로 없고 과제하기도 싫어서(?) 글을 올려본다.

 

문제는 간단히 다음과 같다.

학기가 N일인 경우에 개근상을 받을 수 있는 출결정보의 개수를 세는 문제이다.

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

그 외의 모든 경우는 개근상을 받을 수 있다.

 

---

풀이

문제를 읽어보면 비교적 쉽게 DP인 것을 눈치챌 수 있다. 만약 학기가 N일차이면 N-1일차의 결과를 이용하여 알아낼 수 있기 때문이다. 정답을 1,000,000으로 나눈 나머지를 출력하라는 것을 보면 답이 매우 크다는 의미이다. 여기서 DP를 확신했다.

 

DP배열은 3차원으로 만들었다.

ll dp[1001][2][3];

dp[day][late][absence]이다.

day는 출석일수

late는 지각횟수 (0 or 1의 값을 가질 수 있다.)

absence는 마지막 연속 결석 횟수 (0 or 1 or 2의 값을 가질 수 있다.)

이다.

 

즉, 학기가 n일인 경우 답은 다음과 같다.

for (ll i = 0; i < 2; i++) {
    for (ll j = 0; j < 3; j++) {
        ans += rec(n, i, j);
    }
}

 

재귀함수 내부의 식은 직접 각 경우마다 day-1일까지 가능한 경우를 살펴보며 계산해보자!

---

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, ans = 0;
ll mod = 1000000;
ll dp[1001][2][3];
// dp[출결일수][지각수][끝 칸의 연속결석수]

ll rec(ll day, ll late, ll absence) {
    if (day <= 0) return 0;
    ll& ret = dp[day][late][absence];
    if (ret != -1) return ret; //메모이제이션 이용

    if (late) {//지각을 1회하면서 개근상을 받는 경우의 수 계산
        if (absence == 0) {//마지막날이 결석이 아닌 경우
            ret = rec(day - 1, 0, 0) + rec(day - 1, 0, 1) + rec(day - 1, 0, 2);
            ret += rec(day - 1, 1, 0) + rec(day - 1, 1, 1) + rec(day - 1, 1, 2);
        }
        else if (absence == 1) {//마지막날은 결석, 마지막날의 전날은 결석이 아닌 경우
            ret = rec(day - 1, 1, 0);
        }
        else if (absence == 2) {//마지막날, 마지막날의 전날이 결석인 경우
            ret = rec(day - 1, 1, 1);
        }
        ret %= mod;
        return ret;
    }

    if (!late) {//지각없이 개근상을 받는 경우의 수 계산
        if (absence == 0) {
            ret = rec(day - 1, 0, 0) + rec(day - 1, 0, 1) + rec(day - 1, 0, 2);
        }
        else if (absence == 1) {
            ret = rec(day - 1, 0, 0);
        }
        else if (absence == 2) {
            ret = rec(day - 1, 0, 1);
        }
        ret %= mod;
        return ret;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    //dp 초기화
    memset(dp, -1, sizeof(dp));

    //기저조건
    dp[1][0][0] = 1;
    dp[1][0][1] = 1;
    dp[1][0][2] = 0;
    dp[1][1][0] = 1;
    dp[1][1][1] = 0;
    dp[1][1][2] = 0;

    cin >> n;
    for (ll i = 0; i < 2; i++) {
        for (ll j = 0; j < 3; j++) {
            ans += rec(n, i, j);
        }
    }
    ans %= mod;
    cout << ans << endl;

    return 0;
}