BOJ 5502번 팰린드롬

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

github : https://github.com/junho0956/Algorithm/blob/master/5502/5502/%EC%86%8C%EC%8A%A4.cpp

 

팰린드롬과 관련된 가장 기본이 되는 문제중 하나입니다.

하나의 스트링을 가지고 팰린드롬이 되기 위해 필요한 단어의 최소 갯수를 알기 위해서는

LCS(https://junho0956.tistory.com/39?category=868069) 에 대한 개념을 알아야합니다.

 

팰린드롬의 특성상 주어진 스트링과 이 스트링을 reverse (뒤집은) 스트링의 공통된 최장 부분문자열의 길이를 알고 있다면 답을 구할 수 있습니다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int dp[5001][5001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n; string str, restr;
    cin >> n >> str;
    restr = str;
    reverse(restr.begin(), restr.end());
 
    int len = str.length();
    for (int i = 0; i < len; i++) {
        for (int k = 0; k < len; k++) {
            if (str[i] == restr[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << n - dp[len][len];
    return 0;
}