[백준] 1695번: 팰린드롬 만들기

방법? 규칙을 생각하기가 어려웠던 것 같다. 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));

	}
}