14945 불장난

dfs로는 시간초과 뜬다.

dp top-down, bottom-up 방식 둘다 가능하다.

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, mod = 10007, d[101][101][101];
int dx[] = { 0,1 };
 
int dp(int f, int d1, int d2) {
    if (d[f][d1][d2] != -1) return d[f][d1][d2];
    if (!(!d1 && !d2) && d1 >= d2) return 0;
    if (f == n) return 1;
    int ans = 0;
    for (int i = 0; i < 2; i++) {
        int nd1 = d1 + dx[i];
        for (int j = 0; j < 2; j++) {
            int nd2 = d2 + dx[j];
            ans += dp(f + 1, nd1, nd2);
            ans %= mod;
        }
    }
    d[f][d1][d2] = ans%mod;
    return d[f][d1][d2];
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d", &n);
    printf("%d", (dp(2, 0, 1) * 2) % mod);
    return 0;
}

바로 전 상태만이 현재 상태에 영향을 줄 수 있고 메모리도 줄여볼겸 d[2][][]로 잡았다.

#include <stdio.h>
 
int n, mod = 10007, d[2][101][101], dx[] = { 0,0,-1,-1 }, dy[] = { 0,-1,0,-1 }, i, j, k, l;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) d[n % 2][i][j] = 1;
    for (i = n; i > 0; i--) {
        for (j = 0; j < i; j++) for (k = 0; k < i; k++) d[1 - (i % 2)][j][k] = 0;
        for (j = 0; j < i; j++) for (k = j + 1; k < i; k++) for (l = 0; l < 4; l++) {
            int nx = j + dx[l], ny = k + dy[l];
            if (nx < 0 || ny < 0 || (!(!nx && !ny) && nx == ny) || nx >= i - 1 || ny >= i - 1) continue;
            d[1 - (i % 2)][nx][ny] += d[i % 2][j][k];
            d[1 - (i % 2)][nx][ny] %= mod;
        }
    }
    printf("%d", (d[1][0][0] * 2) % mod);
    return 0;
}