[백준 1695] 팰린드롬 만들기 - Java 코드

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

1695번: 팰린드롬 만들기

 

문제

 

이해

앞뒤가 똑같은 번호를 팰린드롬이라 한다.

입력 수가 주어지면, 해당 수열에 몇번의 숫자를 끼워 넣어야 팰린드롬으로 만들수 있는지를 구한다.

이 문제는 이차원 배열 DP를 만들어서 최솟값 메모이제이션을 통해 답을 구한다.

 

풀이

DP 배열은 n x n 크기로 선언후 -1로 채운다.

그리고 입력받은 arr값에 양 끝을 비교해가면서 팰린드롬을 만드는 경우의 수를 계산 해주면 된다.

왼쪽에 팰린드롬을 만드는 경우와, 오른쪽에 끼워넣어 만드는 경우중,

더 작은 경우를 갖는 쪽을 DP배열에 메모이제이션 해준다.

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;
    public static int[] arr;
    public static void main() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;//= new StringTokenizer(br.readLine());
        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 메소드를 보면, 0과 n-1 (맨 끝값)을 재귀적으로 순회하여

최종적으로 더 작은 값을 반환하도록 설계되어있다.

 

left < right 일때만 수행되고, 더 커지는 경우는 배열을 0으로 초기화 한다.

-1이 아니라면, 이미 할당된 해당 값을 리턴해주고

-1이라면,  메모이제이션을 해주는데, 비교하는 양 끝 값이 같은 경우,

팰린드롬이므로 한칸씩 그대로 이동하여 dp함수를 min에 호출해준다.

만약, 두 값이 다르면, 왼쪽에 삽입하는 경우와 오른쪽에 삽입하는 경우를 메소드로 호출하여, 최솟값을 비교반환한다.

 

해당 메소드는 백트래킹 방식으로 구현되어,

결국 재귀적으로 끝까지 들어갔다가 돌아온다.

 

필요한 부분의 메모이제이션이 한번에 일어나는 샘이다.