BOJ 22983 - 조각 체스판
$dp[y][x]=$ $(y,\,x)$ 에서 왼쪽 위로 올라갈 때 최대로 이어질 수 있는 체스판 길이라고 한다면, 정답은 $\displaystyle\sum_{y=0}^{Y-1}\sum_{x=0}^{X-1} dp[y][x]$ 이다.
$dp$를 채우기 위해서 $dp[y][x]=1+Min\left(dp[y-1][x-1],~linear_{up}[y-1][x],~linear_{left}[y][x-1])\right)$ 를 활용해줄 수 있다.
물론 $B,\,W$ 조건이 맞을때만 성립한다. 이건 적절히 배열의 dimension을 나눠주거나 검사해주면서 세야한다.
$linear$ 함수는 일자로 $BWBW$가 연달아서 나오는 것을 위쪽과 왼쪽에 먼저 $O(N^2)$에 구해둔 것으로 이것으로 $dp$ 테이블을 $O(N^2)$ 에 채울 수 있게 해준다.
// (y, x)에서 왼쪽 위로 시작할 때
// 0 -> B로 시작하는 경우
// 1 -> W로 시작하는 경우
// 최대 길이
short Y, X, dp[3001][3001][2], linear[3001][3001][2][2];
vs b;
short fn(short y, short x, short is_w) {
if (b[y][x] == 'W' && !is_w || b[y][x] == 'B' && is_w) return 0;
if (y == 0 || x == 0) return 1;
short &ret = dp[y][x][is_w];
if (~ret) return ret;
return ret = min({fn(y - 1, x - 1, is_w), linear[y - 1][x][0][is_w ^ 1], linear[y][x - 1][1][is_w ^ 1]}) + 1;
}
void solve() {
cin >> Y >> X;
b = vs(Y);
fv(b);
memset(dp, -1, sizeof dp);
memset(linear, -1, sizeof linear);
for (int y = 0; y < Y; y++) {
for (int x = 0; x < X; x++) {
// 위로 가고 B로 시작하는 것
linear[y][x][0][0] = b[y][x] == 'W' ? 0 : (1 + (y == 0 ? 0 : linear[y - 1][x][0][1]));
// 위로 가고 W로 시작하는 것
linear[y][x][0][1] = b[y][x] == 'B' ? 0 : (1 + (y == 0 ? 0 : linear[y - 1][x][0][0]));
// 왼쪽으로 가고 B로 시작하는 것
linear[y][x][1][0] = b[y][x] == 'W' ? 0 : (1 + (x == 0 ? 0 : linear[y][x - 1][1][1]));
// 왼쪽으로 가고 W로 시작하는 것
linear[y][x][1][1] = b[y][x] == 'B' ? 0 : (1 + (x == 0 ? 0 : linear[y][x - 1][1][0]));
}
}
ll ans = 0;
for (int y = Y - 1; y >= 0; y--) {
for (int x = X - 1; x >= 0; x--) {
int is_w = b[y][x] == 'W';
int add = fn(y, x, is_w);
ans += add;
}
}
cout << ans;
}
Comments