BOJ 22983 - 조각 체스판

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;  
}