1695 팰린드롬 만들기

앞에서 부터 보나 뒤에서 부터 보나 같은 수열인 수열을 팰린드롬 이라고 한다.
이 때 주어진 수열에서 숫자를 몇개 끼워넣어 팰린드롬을 만든다고 할 때,  끼워넣는 숫자의 최소개수를 구하는 문제이다.

이 문제는 혼자힘으로 풀지못해 스터디 그룹에서 해결방법을 알아냈는데, 재귀를 이용한 방법이었다.

수열의 양 끝 숫자가 같으면 양 끝 범위를 1씩 줄여서 재귀하고,
다르면 왼쪽에서 하나를 줄여서 재귀 한것과, 오른쪽에서 하나를 줄여서 재귀한것 중 최솟값에서 1을 더한값을 그 범위의 최소개수로 삼는다.

단순히 이렇게 재귀하면 TLE가 뜨게 되므로 DP를 이용해주면 ACCEPT를 받을 수 있다.
다만 이 방법은 메모리와 시간을 꽤 많이 잡아먹는 방법이다. 다른 풀이방법은 O(n^2)으로 풀 수 있는듯 하다.

소스