[백준]1695번 팰린드롬 만들기 2️⃣

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

• 이전에 풀었던 문제인데 당시에 풀지 못해서 다른 사람 풀이를 봤었다. 다시 풀어보았다.

내 머리속에 항상 먼저 드는 생각은 투포인터이다....;.
1. left, right라는 두개의 포인터를 , 주어진 수의 sequence arr의 양 쪽을 가리키도록 둔다.
1-1. 만약 arr[left]!=arr[right]인 경우, left, right 둘 중 하나를 선택하여 반대편에 삽입한다.
💥 그런데, 이 것을 생각하지 못하겠었다. left, right중 어떤 것을 선택하여야지 "최소의 개수"가 나오는 경우가 나오는 것인지를 모르겠었다.

이를 DP로 풀면 되는 문제였다... 이걸 보고 어떻게 DP를 떠올리는 걸까..? 아무래도 N의 최대 길이가 5000이고, 결국 arr[left]!=arr[right]일 때 마다, 두 경우를 모두 해보는 식으로 단순 구현한다면 2^5000 가지가 나올 수 있을 테니, subproblem이 존재함을 인지하고, 동적 프로그래밍을 생각해야 하는 것 같다..

• dp[i][j]는 left를 i, right를 j로 할 때, 팰린드롬을 만들기 위해 끼워넣는 최소의 개수를 저장하는 cache라고 생각한다.
• 따라서, if arr[left]!=arr[right] --> dp(left+1,right)와 dp(left,right-1) 두 경우를 모두 호출하여, 둘 중 최소 값을 갖는 경우를 채택하면 되는 것이다.
  • left나 right 둘 중 하나에 있는 수를 반대편에 삽입하는 것을 의미한다.
  • 따라서 dp(left+1,right) +1 과 dp(left,right-1)+1을 비교해야한다. 한 개를 삽입하는 것이니까.
• arr[left] == arr[right] 인 경우에는, 어떤 수를 삽입할 필요가 없기에, left, right 모두 다음 대상으로 이동시킨다.
• 언제까지? left < right 인 때 까지만 반복한다.

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

public class Main{
    public static int n;
    public static int[][] dp = new int[5000][5000];
    public static int[] arr = new int[5000];
    public static void Setting() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;//= new StringTokenizer(br.readLine());
        n = Integer.parseInt(br.readLine());
        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());
        }
    }

    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 = dp(left+1,right)+1;
            min = Math.min(min,dp(left,right-1)+1);
        }
        return dp[left][right]=min;
    }
    public static void main(String[] args) throws IOException {
        Setting();
        int res = dp(0,n-1);
        System.out.println(res);

    }
}