https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 서로 다른 방식의 두 가지 dp로 문제를 풀어보았다. 실행 시간은 1번 방법이 2번 방법보다 두 배 정도 더 빨랐다. 1. LCS를 활용한 방법 당연한 이야기지만 기존 문자열에 문자를 추가해 팰린드롬을 만든다면 추가할 문자는 기존에 존재하는 문자 중 하나에 대응하는(팰린드롬 상에서) 문자일 것이다. 그런데 여기서 문자를 추가하는 것은 추가할 문자에 대응하는 문자를 삭제하는 것과 동일하다. 따라서 최소 횟수를 구하는..