[1563] 개근상

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

이 문제는

두가지로 dp를 정의해보았습니다.

첫번째로 풀 때는

dp[날짜][지각 수][현재 날짜의 전 전에 결석했는지][현재 날짜의 전 날에 결석했는지]

라고 처음에 정의했습니다.

근데 이 방법보다 간단하게 정의할 수 있습니다.

3차원 dp인데요

dp[날짜][지각 수][연속으로 결석한 수] 라고 정의할 수 있습니다.

연속으로 결석한 수 라고 정의한 이유는

결석한 수가 연속이지 않으면 0으로 초기화하면 되기 때문입니다.

아래는 두번째 방법 풀 코드입니다.

#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][2][3];
int n;
 
int f(int date, int late, int absence) {
    if (late == 2) return 0;
    else if (absence == 3) return 0;
    
    if (date == n) return 1;
        
    int &ret = dp[date][late][absence];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(date + 1, late + 1, 0) + f(date + 1, late, absence + 1) + f(date + 1, late, 0);
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0);
    return 0;
}
 

이 아래는 첫번째 방법입니다.

#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][3][2][2];//date/late/1 2 3 
int n;
 
int f(int date, int late, int pprev, int prev) {
    if (date == n) return 1;
    int &ret = dp[date][late][pprev][prev];
    if (ret != -1) return ret;
    ret = 0;
 
    if (pprev && prev) {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
    else {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 1) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0, 0);
    return 0;
}