방법? 규칙을 생각하기가 어려웠던 것 같다. min(시작 숫자를 시작으로 하는 팰린드롬을 만드는 데 필요한 개수, 마지막 숫자를 끝으로하는 팰린드롬을 만드는 데 필요한 개수)
+ 안 쪽의 수열을 팰린드롬으로 만들기 위한 개수 가 전체 정답이라는 생각을 하기가 어려웠다ㅜ 아무튼 이것만 알면 재귀함수를 이용해서 쉽게 풀 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Boj1695 {
static int[][] dp;
static int[] arr;
static int solve(int start, int end) {
if (dp[start][end] != -1)
return dp[start][end];
if(start == end) {
return 0;
} else if (start+1 == end) {
if(arr[start] == arr[end])
return 0;
return 1;
}
if(arr[start] == arr[end]) {
return dp[start][end] = solve(start+1, end-1);
} else {
return dp[start][end] = Math.min(solve(start, end-1), solve(start+1, end)) + 1;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());
arr = new int[N];
dp = new int[N][N];
for(int i = 0; i < N; i++)
Arrays.fill(dp[i], -1);
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.println(solve(0, N-1));
}
}