BOJ 15770 - QueryreuQ
팰린드롬을 만들기 위해 이것저것 생각해야한다.
내 방법은 좀 느린방법인데 다음과 같다.
$N \le 10000$ 이므로 $O(N^2)$ 을 믿자.
$dp[i]=i$ 번째가 가장 오른쪽 팰린드롬 위치인 팰린드롬들의 가장 왼쪽 인덱스라 하자.
즉, $dp[i]$에 있는 인덱스들의 문자는 $i$의 문자와 같아야한다.
어떤 문자 $c$를 추가할 때, 현재 길이가 $i$ 라면 $dp[i]$를 모두 조사해서 그것의 바로 왼쪽이 $c$ 가 나오는 것들을 $dp[i+1]$ 에 추가하고 문자열에 $c$를 추가한다.
삭제는 반대로 한다.
Comments