[백준 5502 펠린드롬 문제] PYTHON

 

아래의 LCS 알고리즘의 점화식만 안다면 쉽게 풀 수 있는 문제다.

만약 두 알파벳이 같을때, dp[i][j] = dp[i -1][j - 1] +1

두 알파벳이 다를때는 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 

 

 

https://gusdnr69.tistory.com/192

LCS 알고리즘이란? (최장 공통 부분 수열)

 

import sys

input = sys.stdin.readline
N = int(input())
M = list(input().rstrip())
ON = 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] != ON[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])

참고로 pypy로 해야 풀 수 있다.