[5502] 팰린드롬

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

---

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String st1 = sc.next();
		String st2 = new StringBuffer(st1).reverse().toString();
		int[][] DP = new int[N+1][N+1];
	
		for(int i=0; i<st1.length(); i++) {
			for(int j=0; j<st2.length(); j++) {
				if(st1.charAt(i) == st2.charAt(j)) {
					DP[i+1][j+1] = DP[i][j] + 1;
				} else {
					DP[i+1][j+1] = Math.max(DP[i][j+1], DP[i+1][j]);
				}
			}
		}
		
		System.out.println(N-DP[N][N]);
		
	
	}
}

---

주어진 문자열에서 팰린드롬을 만들기 위해 삽입해야 하는 문자개수의 최솟값을 구하는 문제입니다. 주어진 문자열에서 가장 긴 팰린드롬을 찾아서 문자열의 길이에서 빼주면 답을 구할 수 있습니다. 저는 여기까지 생각은 했는데 어떻게 문자열에서 가장 긴 팰린드롬을 찾을지 생각해봤는데 결국 어떻게 찾는지 생각을 해내지 못했습니다. 그래서 검색을 해봤는데 제가 며칠 전에 풀었던 LCS 를 이용하면 풀 수 있었습니다.

LCS 는 최장 공통 부분 수열이라는 뜻으로 두 문자열이 주어졌을 때 부분 수열이 되는 문자 중 가장 긴 문자열을 찾는 알고리즘입니다. 근데 팰린드롬을 여기에 적용하면 하나의 문자열은 주어진 문자열, 두 번째 문자열은 문자열을 뒤집은 상태로 두 문자열을 LCS 하면 가장 긴 팰린드롬이 나오게 됩니다. 이러한 문제 유형은 정해져 있는 유형이므로 LCS 알고리즘은 외우고 있어야 된다고 생각했습니다.

[ 문제 풀이 ]

1. st1 에는 주어진 문자열, st2 에는 주어진 문자열을 뒤집은 문자열을 저장합니다. Java 에서는 StringBuffer 를 사용해서 문자열을 뒤집을 수 있습니다.

2. st1과 st2 를 LCS 알고리즘으로 2차원 DP 에 저장하여 st1의 길이에서 빼면 정답입니다.