[백준] 1695번. 팰린드롬 만들기(JAVA)

문제

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

---

풀이(30분)

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

public class Main {

    static int n;
    static int[][] dp;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        n = Integer.parseInt(br.readLine());
        dp = new int[n+1][n+1];
        arr = new int[n+1];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],-1);
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int res = dp(0,n-1);
        System.out.println(res);
    }

    public static int dp(int left, int right){
        if(left>=right){
            return 0;
        }
        
        // 탐색된 적이 있다면 반환
        if(dp[left][right]!=-1){
            return dp[left][right];
        }
        
        int min = 0;
        
        // 팰린드롬이라면 양쪽 인덱스 모두 변경
        if(arr[left]==arr[right]){
            min =dp(left+1,right-1);
        }else{ // 팰린드롬이 아니라면 양쪽에 대해 모두 비교
            min = Math.min(dp(left+1,right)+1 ,dp(left,right-1)+1);
        }
        return dp[left][right]=min;
    }
}

---

문제 풀이 전략

 

양쪽 인덱스를 모두 변경해 가며 dp를 통해 메모이제이션 하는 방식이다.

 

양쪽 인덱스를 모두 봐야하는 예시는 다음과 같다.

 

1. 양쪽 인덱스 변경에 대해 똑같은 경우

ex) 1 2 3 의 경우 1 2 3 2 1이 될 수도 있고, 3 2 1 2 3이 될 수도 있다.

 

2. 양쪽 인덱스 변경에 대해 다른 경우

ex) 1 1 3의 경우 오른쪽만 보면 1 1 3 1 1로 만들어야 하지만, 왼쪽을 본다면 3 1 1 3 같은 경우도 가능하다.