[백준] 1695번 - 팰린드롬 만들기 (Gold 4)

문제 링크

백준 1695번 - 팰린드롬 만들기 (Gold 4)

문제 설명

앞에서부터 뒤로 보나, 뒤에서부터 앞으로 보나 같은 수열을 팰린드롬이라고 한다.
수열이 주어졌을 때, 이 수열에 가장 적은 개수의 수들을 끼워넣어 팰린드롬으로 만드려고 한다.
필요한 최소의 수를 구하시오.

정답 코드 및 설명

DP를 사용하여 풀이한다.
원래 수열 arr의 i번째 원소부터 j번째 원소까지로 이루어진 부분 수열을 생각하자.
이 부분 수열을 팰린드롬으로 만들기 위한 수들의 최소의 개수를 makePalindrom[i][j]라고 하자.

길이가 1인 부분수열은 이미 팰린드롬이므로, 수를 더 추가할 필요가 없다.
첫 원소가 (i-length)번째 원소이고 마지막 원소가 (i - 1)번째 원소인 길이가 length인 부분수열을 생각하자.
크게 세 가지 경우로 나누어진다.

1. 첫 원소 arr[i - length]과 마지막 원소 arr[i - 1]이 다른 경우
   • 최소의 개수의 수를 추가해서 팰린드롬을 만드는 방법에는 두 가지 후보가 있다.
   • 맨 앞에 arr[i - 1]을 추가하는 경우 : makePalindrom[i - length][i - 2] + 1
   • 마지막에 arr[i - length]를 추가하는 경우 : makePalindrom[i - length + 1][i - 1] + 1
   • 둘 중 작은 값이 makePalindrom[i - length][i - 1]이 된다.
2. 길이가 2보다 크고, 첫 원소 arr[i - length]와 마지막 원소 arr[i - 1]이 같은 경우
   • 첫 원소와 마지막 원소를 빼고 생각해도 동일하다.
   • makePalindrom[i - length][i - 1] = makePalindrom[i - length + 1][i - 2]
3. 길이가 2이면서 첫 원소 arr[i - length]와 마지막 원소 arr[i - 1]이 같은 경우
   • 이미 팰린드롬이므로 makePalindrom[i - length][i - 1] = 0

이를 코드로 구현하면 아래와 같다.
배열의 크기가 $N^2$이고 각각의 값을 구하는데는 상수시간이 들어가므로, 전체 시간 복잡도는 $O(N^2)$이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1695 {
    int[] arr;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }

    int dp() {
        // makePalindrom[i][j] : arr[i]~arr[j] 부분수열에 대한 답
        int[][] makePalindrom = new int[arr.length][arr.length];
        for (int length = 2; length <= arr.length; length++) {
            for (int i = length; i <= arr.length; i++) {
                if (length > 2 && arr[i - length] == arr[i - 1]) {
                    makePalindrom[i - length][i - 1] = makePalindrom[i - length + 1][i - 2];
                }
                if (arr[i - length] != arr[i - 1]) {
                    makePalindrom[i - length][i - 1] = Math.min(makePalindrom[i - length][i - 2],
                            makePalindrom[i - length + 1][i - 1]) + 1;
                }
            }
        }
        return makePalindrom[0][arr.length - 1];
    }

    void solution() throws IOException {
        input();
        System.out.println(dp());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1695().solution();
    }
}