[BOJ] 1695 : 팰린드롬 만들기(Java)

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

문제 링크 : https://www.acmicpc.net/problem/1695

---

💡 풀이

앞, 뒤로 보았을 때 숫자가 같아야하기 때문에 두 포인터(Two Pointer)를 사용했다.

앞의 시작을 L, 뒤의 시작을 R이라 두고 시작한다. 이때 시작의 L, R은 각각 0, N-1이 된다. 

만약 주어진 숫자의 L 번째, R 번째 숫자가 같다면, L+1, R-1을 통해 한 자리 씩 줄여 나아간다. 만약 이 두 숫자가 다를 경우, 숫자를 끼워 넣어 추가해야 한다. 이때 L을 1 증가시키는 방법과 R을 1 감소 시키는 방법, 이 두 가지의 경우가 존재한다. 
재귀를 통해 이 둘 중 끼워 넣을 수가 최소인 값을 반환하도록 한다. 여기서 다이나믹 프로그래밍을 사용하여, L ~ R의 범위에서 끼워 넣을 수가 최소인 것의 개수를 저장하여 반환하도록 했다. 

 

전체적인 코드는 다음과 같다. 

import java.util.Arrays;
import java.util.Scanner;

public class Q1695 {
    static int N;
    static int[] numbers;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = sc.nextInt();
        }

        dp = new int[N][N];
        for (int[] ints : dp) {
            // dp의 초기값을 -1로 저장
            Arrays.fill(ints, -1);
        }

        int L = 0;
        int R = N - 1;
        System.out.println(recur(L, R));
    }

    static int recur(int L, int R) {
        // 기저 사례 : L이 R보다 크면 종료 
        if (L > R) {
            return 0;
        }

        // dp[L][R]에 값이 저장되어 있다면, 바로 반환하고 종료
        if (dp[L][R] != -1) {
            return dp[L][R];
        }

        if (numbers[L] == numbers[R]) {
            dp[L][R] = recur(L + 1, R - 1);
        } else {
            dp[L][R] = Math.min(recur(L + 1, R) + 1, recur(L, R - 1) + 1);
        }

        return dp[L][R];
    }
}