1695번. 팰린드롬 만들기

 

아이디어

어떤 수열을 팰린드롬으로 만들기 위해 기본적으로 생각해볼 수 있는 과정은 다음과 같다.

 

1. 시작 숫자와 끝 숫자가 다른 경우

시작 숫자를 끝에 추가 후 시작 index + 1

or 끝 숫자를 시작에 추가 후 끝 index - 1

 

 

2. 시작 숫자와 끝 숫자가 같은 경우

시작 index + 1, 끝 index - 1 로 이동

 

문제는 1번 케이스에서 전자와 후자 중 어떤 방식을 취하는 것이 최소가 되는 방식인 지를 알아내야 하는 것인데 이 때 dp 를 활용하면 된다.

 

dp[i][j] 에서 i 를 시작 index, j 를 끝 index 로 바라보면

numbers[i] != numbser[j] 일 때

dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1

 

numbers[i] == numbers[j] 일 때

dp[i][j] = dp[i + 1][j - 1]

 

 

와 같은 점화식을 정의할 수 있다.

 

i == j 인 경우 숫자가 1개 이므로 dp[i][j] = 0 이 되고, i >= j 인 경우 탐색할 수 없는 케이스이므로 0 을 할당해준다.

 

풀이코드

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

public class _n1695_ {

    static int[] numbers;
    static int[][] dp;

    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());

        numbers = new int[N];
        dp = new int[N][N];

        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
            Arrays.fill(dp[i], -1);
        }

        int result = dp(0, N - 1);
        System.out.println(result);
    }

    public static int dp(int i, int j) {
        if (i >= j) {
            return 0;
        }

        if (dp[i][j] != -1) { // 값을 한 번 구했다면 추가 재귀 필요 X
            return dp[i][j];
        }

        if (numbers[i] == numbers[j]) {
            dp[i][j] = dp(i + 1, j - 1);
        } else {
            dp[i][j] =  Math.min(dp(i + 1, j), dp(i, j - 1)) + 1;
        }

        return dp[i][j];
    }
}