[백준 알고리즘] 5502번 팰린드롬 만들기. 파이썬(python)

 

LCS(최장 공통 부분 수열)을 이용해 -> 원래 문자열과 뒤집은 문자열 비교

전체개수(n)-LCS길이(dp[-1][-1])

 

import sys
input=sys.stdin.readline

n=int(input())
m=list(input().strip())
reverse_m=m[::-1]
dp=[[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if m[i-1]!=reverse_m[j-1]:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j-1]+1
print(n-dp[-1][-1])