I. Stains

$1 \times 1$ 크기의 격자 $MN$ 개가 $M \times N$ 크기의 직사각형을 이루고 있다. 각 격자에는 얼룩이 묻어있을 수 있다. $3 \times 3$ 크기의 덮개를 써서 모든 얼룩을 덮고자 할 때, 필요한 덮개의 최소 개수를 구하는 문제다.

이 문제에서 중요한 것은 $M$ 제한이 $N$ 제한에 비해 현저히 작다는 점이다.

한 열에 덮개를 배치하는 경우의 수를 생각해보자. 우선 최악의 경우를 고려하기 위해 $M=10$이라 생각하자. 하나의 덮개를 덮개의 가장 윗 행 번호로 표현하자. 같은 행 번호에 여러 덮개가 있으면 항상 비효율적이며, 9번 행과 10번 행으로 표현되는 덮개는 없다. 따라서 $2^8 = 256$가지를 생각할 수 있다.

좀 더 경우의 수를 줄여보자. 10개의 행을 모두 덮는 경우를 제외하고 덮개가 덮는 구간이 서로 겹치면 항상 비효율적임을 알 수 있다. 이처럼 경우를 간추리면 경우의 수는 29가지가 된다. 이제 간추린 경우의 수를 이용해 아래와 같이 Dynamic Programming을 할 수 있다.

D[i][j][k] = 1~i번째 열까지 모든 얼룩을 덮었고, i-1 열에 덮개가 j로 놓여있고, i 열에 덮개가 k로 놓여있을 때 이용한 덮개의 최소 개수

점화식은 아래와 같다.

D[i][j][k] = min(D[i-1][l][j] + C[k])

(단, i-2 열에 덮개가 l 처럼 있고, i-1 열에 덮개가 j 처럼 있고, i 열에 덮개가 k 처럼 있을 때 i열에 있는 모든 얼룩을 덮어야한다.)

여기서, C[k] = k로 덮개를 놓을 때 이용한 덮개의 수이며, l은 임의의 한 덮개 배치다.

덮개 배치의 가능한 경우의 수를 $K = 29$로 나타내면 총 시간복잡도는 $O(NK^3)$이 된다.

#include <stdio.h> int T, N, M, K, XX; int A[1001], D[1001][29][29]; int bitcnt[29], idx_to_msk[29]; bool V[8]; void dfs(int n) { if (n >= 8){ int msk = 0, i; for (i=0;i<8;i++) bitcnt[XX] += V[i]; for (i=0;i<10;i++){ if (V[i] || (i > 0 && V[i-1]) || (i > 1 && V[i-2])) msk |= (1<<i); } idx_to_msk[XX++] = msk; return; } dfs(n+1); V[n] = 1; dfs(n+3); V[n] = 0; } int main() { int i, j, k, l; dfs(0); bitcnt[XX] = 4; idx_to_msk[XX++] = 1023; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &M, &N, &K); for (i=1;i<=N;i++) A[i] = 0; while (K--){ int x, y; scanf("%d%d", &x, &y); A[y] |= (1<<(--x)); } for (i=0;i<=N;i++) for (j=0;j<XX;j++) for (k=0;k<XX;k++) D[i][j][k] = 2e9; D[0][0][0] = 0; int ans = 2e9; for (i=0;i<=N;i++) for (j=0;j<XX;j++) for (k=0;k<XX;k++) if (D[i][j][k] < 2e9){ if (i == N){ if (ans > D[i][j][k]) ans = D[i][j][k]; continue; } int msk = idx_to_msk[j] | idx_to_msk[k]; for (l=0;l<XX;l++){ int nmsk = msk | idx_to_msk[l]; int v = bitcnt[l]; if ((nmsk | A[i+1]) == nmsk){ if (D[i+1][k][l] > D[i][j][k] + v) D[i+1][k][l] = D[i][j][k] + v; } } } printf("%d\n", ans); } }