1695 - 팰린드롬 만들기

처음에 그리디적으로 접근했는데, 이게 발상의 시초였다.

팰린드롬을 만들 때, 좌우 한쪽을 기준으로 잡고, 양쪽이 다르면 반대쪽에 "그 문자"를 추가한다고 생각해보았다. 예를 들면,

abaacd 라면 가장 왼쪽 a와 잡고 가장 오른쪽은 d를 비교한다. 이 때 문자가 서로 다르므로 오른쪽에 a를 추가하여 abaacda 를 만든다고 생각한다. a는 이제 추가했으므로 b를 잡고 다시 d를 비교한다. 다르므로 다시 추가하면 abaacdba 가 될 것이다.

이 행동을 반복하면

abaacdaba

abaacdaaba

abaacdcaaba

abaacdcaaba

하지만 위 방법은 너무 그리디적이여서 만약 번갈아서 추가해야하는 상황이 생기면 틀리게 된다.

생각을 살짝 바꾼다면, L번째와 R번째를 비교하는 함수를 p(L, R) 이라 하자.
p(L, R) 에서 나올 수 있는 경우는 3가지이다.

1. L과 R이 같은 경우

2-1. L과 R이 다를 때, p(L+1, R)에서 답이 나오는 경우 + 1 (여기서 1은 한쪽이 다르므로 문자를 추가한 비용)

2-2. L과 R이 다를 때, p(L, R-1)에서 답이 나오는 경우 + 1

우리는 이제 그리디적인 2-1 과 2-2 에 대해 유연하게 대처할 수 있게 되었다.

중복되는 연산이 굉장히 많으므로 [L][R]과 같이 저장해서 중복연산을 피하면 되겠다.