[BOJ][1563] 개근상

[ 오늘의 문제 한줄평 ]
언제쯤 DP를 술술 풀까

개근상

나름 DP로 풀 알고리즘..까지는 아니지만 방법은 생각해 내서 뿌듯

but 초기 DP 배열 설정을 잘못했고, 시간초과 해결 방법을 아직도 이해 못했음
그리고 이제 그냥 대충 들어오는 값 상한선들 정해지면 배열 MAX로 때려버리자. 귀찮다

문제를 DP로 어떻게 풀어야 할 것인가는 생각을 잘 했다. 내일의 출결이 오늘의 출결에 따라 3가지로 나뉘니까.. 근데 그걸 코오딩을 하는걸 못했음.

그리고 시간초과를 왜 저렇게 해결하는지를 모르겠음. 왜일까?!?!?!!!?

#include <iostream>
#include <cstring>
using namespace std;

int D[1001][3][4];

int solve(int n, int day, int l, int a)
{
    if(l >= 2 || a >= 3)
        return 0;
    if(n == day)
        return 1;

    // 왜 이친구를 추가해야만 시간초과가 없어지는 것일까...... 그리고 왜 D[day][l][a]일까...
    // 그날 경우의 수를 다 더해야 하는거 아닌가......... 아닌가.....
    if(D[day][l][a] != -1)
        return D[day][l][a];

    return D[day][l][a] = (solve(n, day + 1, l, 0) + solve(n, day + 1, l + 1, 0) + solve(n, day + 1, l, a + 1)) % 1000000;
}

int main()
{
    int N;
    cin >> N;
    memset(D, -1, sizeof(D));

    cout << solve(N, 0, 0, 0);
}