AOJ 파스타 5546

DP

SOL) 저기 보이는 복잡한 if문: 해당 날에 n 파스타를 먹을 수 있으면 먹고 아니면 패스
        3차 배열을 사용한 이유를 잘생각 단순히 2차배열로는 모든 정보를 확실히 표현이
        불가능 하다.
[-] Collapse

#include<cstdio>
#include<cstring>
int arr[105];
int n, k;
int cache[4][4][105];
int count(int day, int pasta, int before){
    if (arr[day] != 0) return count(day + 1, 0, arr[day-1]);
    int& ret = cache[before][pasta][day];
    if (day == n + 3) return ret = 1;
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 1; i <= 3; i++){
        if (!((arr[day - 1] == i && arr[day + 1] == i)
            || (arr[day - 1] == i && arr[day - 2] == i)
            || (arr[day + 1] == i && arr[day + 2] == i))){
            arr[day] = i;
            ret += count(day + 1, i, arr[day-1]);
            ret %= 10000;
            arr[day] = 0;
        }
    }
    return ret % 10000;
}
int main(){
    memset(cache, -1, sizeof(cache));
    scanf("%d%d", &n, &k);
    while (k--){
        int day, pNum; scanf("%d%d", &day, &pNum);
        arr[day + 2] = pNum;
    }
    printf("%d", count(3, 0, 0)%10000);
    return 0;
}