BOJ 10759 - 팰린드롬 경로 3

BOJ 10759 - 팰린드롬 경로 3

꽤나 오래 고민해서 풀었다.

해법만 쓰겠다. USACO 정해와 동일하게 잘 풀어서 만족스럽다.

$dp[len][y1][y2]=$길이 $len \cdot 2 + 1$ 의 팰린드롬인데, 중앙 대각선이 중심이고 각각 끝나는 지점이 왼쪽 위는 $y1$, 오른쪽 아래는 $y2$ 인 팰린드롬의 개수

그러면 정답은 $dp[0][0][n-1]$ 이다.

$O(n^3)$ 에 풀리는 문제이고 토글링을 이용해 $O(n^2)$ 의 공간복잡도로 풀어야 한다.

점화식은 그렇게 복잡하진 않지만 $y1, y2, len$ 를 갖고 $x1, x2$ 를 역으로 얻어와서 계산에 써주고 다시 저장할 땐 $y$ 들에 대해서만 저장을 해야하는 것이 구현이 헷갈린다.

---

이 문제를 해결할 때 $dp[2][501][501]$ 로 해주고, 토글링을 해주는 과정에서 이전 배열에 있던 값을 초기화해주지 않았더니 틀리는 문제가 발생했다.

토글링을 써줄 때 이전 배열을 초기화시켜줘야 하는지 여부를 꼼꼼히 따져보는 것이 필요할 것 같다.

웬만하면 초기화를 하는 습관을 들여도 괜찮을지도

---

const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
  
int dp[2][501][501];  
  
void solve() {  
   int n;  
   cin >> n;  
   vs b(n);  
   fv(b);  
  
   for (int y = 0; y < n; y++) dp[(n - 1) & 1][y][y] = 1;  
  
   auto add = [&](int &i, int b) {  
      i = md(i + b);  
   };  
  
   auto get_y2 = [&](int len, int x2) {  
      return n - 1 - (len - (n - 1 - x2));  
   };  
  
   for (int len = n - 2; len >= 0; len--) {  
      int C = len & 1, P = C ^ 1;  
      for (int y1 = 0; y1 <= len; y1++) {  
         int x1 = len - y1;  
         for (int y2 = n - 1; y2 >= n - 1 - len; y2--) {  
            int x2 = get_y2(len, y2);  
            // 팰린드롬을 만들 수 없으면  
            if (b[y1][x1] != b[y2][x2]) continue;  
            // right - left  
            if (b[y1][x1 + 1] == b[y2][x2 - 1]) add(dp[C][y1][y2], dp[P][y1][get_y2(len + 1, x2 - 1)]);  
            // right - up  
            if (b[y1][x1 + 1] == b[y2 - 1][x2]) add(dp[C][y1][y2], dp[P][y1][y2 - 1]);  
            // down - left  
            if (b[y1 + 1][x1] == b[y2][x2 - 1]) add(dp[C][y1][y2], dp[P][y1 + 1][get_y2(len + 1, x2 - 1)]);  
            // down - up  
            if (b[y1 + 1][x1] == b[y2 - 1][x2]) add(dp[C][y1][y2], dp[P][y1 + 1][y2 - 1]);  
         }  
      }  
      for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) dp[P][y][x] = 0;  
   }  
   cout << dp[0][0][n - 1];  
}