백준 2079번: 팰린드롬

문제 설명

• https://www.acmicpc.net/problem/2079
• 입력으로 들어온 단어를 최소 몇개의 팰린드롬으로 나눌 수 있는지 구하는 문제입니다.

접근법

• 팰린드롬 판별: 왼쪽끝과 오른쪽 끝에서 시작해 두 문자가 다르면 팰린드롬이 아닙니다.
• dp[i] = i까지의 문자를 고려해서 만들 수 있는 최소 팰린드롬 개수입니다.
  입력이 [a,n,a,b,a,n] 일 때 dp는 [1,2,1,2,3,2]입니다.
  anaba까지의 dp([1,2,1,2,3])가 구해진 상태에서 n을 추가해 판별해 보겠습니다.
  n은 앞에서부터 자신이 팰린드롬이 될 수 있는지 확인합니다. anaban, _naban, __aban, ___ban,____an,_____n
  이때 _naban은 팰린드롬이 됩니다. 그리고 앞에 있는 _를 다시 구하지 않습니다. 이미 앞선 계산에서 해당 최적값을 구했기 때문에 dp에서 값을 꺼내 씁니다.
  _naban에서 왼쪽 n의 인덱스를 j라고 할 때 dp[j-1]과 naban이라는 하나의 팰린드롬을 더한 dp[j-1]+1이 dp[i]가 됩니다.
  위 예에서는 등장하지 않지만 j에따라 여러 팰린드롬이 나올 수 있습니다. xababa는 ababa도 팰린드롬이지만 aba도 팰린드롬입니다. 그래서 Math.min을 사용해야 합니다.
• 팰린드롬을 판별하는 함수에 s.substring()으로 문자열을 넘겼더니 메모리 초과가 발생했습니다. 문자열을 계속 만드는 작업은 메모리에 부담이 가기 때문에 substring하지 않고 문자의 인덱스만 넘겨주는게 좋습니다. (어차피 팰린드롬 판별 함수에서 .charAt()밖에 하지 않으므로 상관 없습니다.)
• 결론: if s.substring(j,i) is parlindrome, then dp[i] = Math.min(dp[j-1]+1, dp[i])

정답

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int N = s.length();
		int[] dp = new int[N+1];
		Arrays.fill(dp, 2001);
		dp[0] = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= i; j++) {
				if(isPalindrome(j,i,s)) {
					dp[i+1] = Math.min(dp[i+1],dp[j]+1); 
				}else {
					dp[i+1] = Math.min(dp[i+1],dp[i]+1);
				}
			}
		}
		System.out.println(dp[N]);
	}
	public static boolean isPalindrome(int leftIdx, int rightIdx, String s) {
		while(leftIdx<=rightIdx) {
			if(s.charAt(leftIdx) != s.charAt(rightIdx)) return false;
			leftIdx++;
			rightIdx--;
		}
		return true;
	}
}