BOJ 5502 팰린드롬

https://www.acmicpc.net/problem/5502

5502번: 팰린드롬

 

딱 보고 아 이거 이차원 dp네 라고 생각했는데 그 이후로 한 이틀간 못 풀었습니다...

 

은둔고수 님이 저에게 완성된 팰린드롬에서 뺀다고 생각해 보라고 힌트를 주셨는데, 그거 듣고 조금 고민하다가 풀었습니다.

 

$dp(i, j)$는 $i$번째 문자와 $j$번째 문자가 같으면 $dp(i+1,j-1)$이고 다르면 $min(dp(i+1, j), dp(i, j-1)) + 1$이 됩니다.

 

cologne 님이 처음에 원래 문자열과 뒤집은 문자열의 LCS를 구하면 된다고 했었는데, 굉장히 그럴듯한 풀이라 속을 뻔 했습니다. 은둔고수 님이 틀렸다고 말해주시지 않았으면 짜러 갈 뻔 했습니다. 근데 사실 왜 틀렸는지 아직 몰라요.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, memo[5050][5050];
string s;
vector<int> vec;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> s;

    for (int k = 0; k < n; k++) {
      for (int i = 0; i + k < n; i++) {
        int j = i + k;
        if (s[i] == s[j]) {
          if (k == 0) continue;
          memo[i][j] = memo[i + 1][j - 1];
          continue;
        }
        memo[i][j] = min(memo[i + 1][j], memo[i][j - 1]) + 1;
      }
    }

    cout << memo[0][n - 1] << endl;
  }

  return 0;
}