백준 1509 - 팰린드롬 분할

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String s = br.readLine();
        int s_length = s.length();
        boolean [] [] check = new boolean [s_length] [s_length];

        // 1자리는 무조건 펜린드롬 가능
        for (int i = 0; i < s_length; i++) {
            check[i][i] = true;
        }

        // 2자리는 앞에거랑 같으면 팬린드롬 가능
        for (int i = 1; i < s_length; i++) {
            if (s.charAt(i-1) == s.charAt(i)) check[i-1][i] = true;
        }

        // 3자리 부터는 1자리 2자리에서 구한거를 바탕으로
        for (int i = 0; i < s_length; i++) {
            int c = 1;
            while (true) {
                int left = i - c;
                int right = i + c;
                if (left < 0 || right >= s_length) break;
                if (s.charAt(left) != s.charAt(right)) break;
                check[left][right] = true;
                c++;
            }
        }

        for (int i = 1; i < s_length; i++) {
            if (!check[i-1][i]) continue;
            int c = 1;
            while (true) {
                int left = i - 1 - c;
                int right = i + c;
                if (left < 0 || right >= s_length) break;
                if (s.charAt(left) != s.charAt(right)) break;
                check[left][right] = true;
                c++;
            }
        }
//        for (boolean [] b : check) System.out.println(Arrays.toString(b));

        // 0부터 해당 자리까지의 최대 팬린드롬을 구함
        int [] dp = new int [s_length];
        dp[0] = 1;
        for (int i = 1; i < s_length; i++) {
            dp[i] = dp[i-1] + 1;
            for (int j = 0; j < i; j++) {
                if (check[j][i]) dp[i] = (j == 0) ? 1:Math.min(dp[i], dp[j-1]+1);
            }
        }

//        System.out.println(Arrays.toString(dp));
        System.out.println(dp[s_length - 1]);
    }
}

문자열 길이가 최대 2500이니까 O(N^3)이상은 안된다는 걸 알고 N^2로 해결방법을 구하는 문제

 

팬린드롬인 모든 부분 문자열의 시작, 끝 인덱스를 저장해 두고

 

첫 문자부터 마지막 문자까지 돌면서

 

해당문자가 팬린드롬에 문자에 해당하는게 유리하면 그 팬린드롬이 시작하기 전 인덱스 dp+1 그렇지 않으면 해당 인덱스전의 dp + 1을 해준다.