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

문제 설명

https://www.acmicpc.net/problem/1695

문제 풀이

• 펠린드롬 관련 문제가 좀 생소해서 헤맸다.. 다이나믹 프로그래밍 문제
• 관련 점화식은 아래와 같다.

  DP[a][b] : 인덱스 a 부터 b까지 수열에 최소로 끼워 넣어야하는 숫자의 갯수

  1. arr[a] == arr[b] 일 경우
     DP[a][b] = DP[a+1][a-1]
  2. arr[a] != arr[b] 일 경우
     DP[a][b] = MIN( DP[a+1][b] + 1, DP[a][b-1] + 1 )

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, INF = 987654321;
    public static int[] arr = new int[5000];
    public static int[][] dp = new int[5000][5000];

    //a 부터 b까지 펠린드롬 사이에 끼워 넣어야할 수의 최소 개수
    public static int solve(int a, int b) {
        //기저조건 1 숫자 하나일 경우 -> 결과 : 0
        if (a >= b) return 0;
        if (dp[a][b] != -1) return dp[a][b];
        int res = INF;
        if (arr[a] == arr[b])
            res = solve(a+1, b-1);
        else
            res = Math.min(solve(a+1, b) + 1 , solve(a, b-1) + 1);
        return dp[a][b] = res;
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            Arrays.fill(dp[i], -1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(solve(0, N-1) + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}