백준 - 팰린드롬 만들기

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = arr[i - 1] == arr[N - j] ? 
                        dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        System.out.println(N - dp[N][N]);
    }
}

풀이

LCS를 이용하면 쉽게 풀 수 있는 문제입니다.(해당 아이디어를 떠올리기 쉽지는 않지만....😭)

해당 배열과 해당 배열의 역 순의 LCS를 구해줍니다.
백준의 예제를 이용한다면 1,2,3,4,2 <-> 2,4,3,2,1의 LCS를 구해줍니다.
그렇게 되면 2,3,2가 LCS인 것을 알 수 있는데 해당 값은 팰린드롬의 형태를 가지고 있다는 것을 알 수 있습니다.

결국 해당 값을 제외한 나머지의 값만을 추가해준다면 팰린드롬을 만들 수 있다는 이야기가 되므로 N - LCS값이 정답이 됩니다.

출처 : 백준 - 팰린드롬 만들기