[백준 - 5502번] 팰린드롬 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

입력

첫 번째 줄에는 문자열의 길이 N (3 ≤ N ≤ 5000)이 주어진다. 두 번째 줄에는 길이가 N인 문자열이 주어진다. 문자열은 대문자 'A'-'Z'와 소문자 'a'-'z', 숫자 '0'-'9'로 이루어진다. 대문자와 소문자는 구분되어야 한다.

출력

첫 번째 줄에 삽입해야할 최소 개수를 출력한다.

풀이

팰린드롬을 만들기 위해서 삽입해야될 최소 개수를 구해야 한다.

이 문제를 풀기 위해서 dp를 활용해야 한다.

길이가 3인 팰린드롬을 구한다고 해보자

Ab3bd에서 b3b는

1. Ab을 만드는데 최소 비용 + 맨 앞에 b가 추가되는 경우
2. b3를 만드는데 최소 비용 + 맨 뒤에 A가 추가되는 경우
3. 맨 앞과 맨 뒤가 같다면 3을 만드는데 최소 비용이 든다.

이렇게 3가지 경우로 나눠진다.

그래서 이를 토대로 dp를 정의하면 다음과 같다.
dp[A][B] -> A에서 B까지 팰린드롬을 만드는데 최소 비용

그래서 구간의 길이 2부터 ~ length()까지 반복하면서 각 구간에서 위 3가지 경우 중 가장 작은 값을 넣으면 된다.

이 풀이의 시간 복잡도는 약 O(N^2)이다.

소스 코드

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      String input = br.readLine();
      
      int[][] dp = new int[input.length() + 1][input.length() + 1]; //[A][B] A부터 B까지 팰린드롬을 만드는 최소 비용
      
      for(int i=1; i<=input.length() - 1; i++) {
          if(input.charAt(i - 1) == input.charAt(i)) {
              dp[i][i + 1] = 0;
          } else {
              dp[i][i + 1] = 1;
          }
      }
      
      for(int i=3; i<=input.length(); i++) {
          //3 부터 length()까지 구간 별 최소 비용을 구한다.
          for(int j=1; j <= input.length() - (i - 1); j++) {
              int lastInd = j + (i - 1);
              dp[j][lastInd] = Math.min(dp[j + 1][lastInd] + 1, dp[j][lastInd - 1] + 1); //새로 추가하는 경우의 수
              
              if(input.charAt(j - 1) == input.charAt(lastInd - 1)) {
                  //맨 앞과 맨 뒤가 같은 경우는 재사용 가능
                  dp[j][lastInd] = Math.min(dp[j][lastInd], dp[j + 1][lastInd - 1]);
              }
          }
          
      }
      
      System.out.println(dp[1][input.length()]);
  }
}