b1509. 펠린드롬 분할

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

 

 

 

문자열을 여러 개의 회문으로 분할할 때 최소 회문 개수를 구하는 문제다.

문자열을 한 문자씩 쪼개며 특정 부분이 회문인지 여부를 확인한 후,

최소 회문 분할 수를 계산해나가는 방식으로,

repeat 배열을 통해 각 구간이 회문인지 아닌지를 확인하고,

dp 배열을 사용해 0번째부터 현재 인덱스까지 최소 회문 분할 개수를 저장한다.

 

먼저 입력받은 문자열을 charArr 배열에 저장하고,

문자열의 길이를 len 변수에 저장해 구간 확인을 위한 반복문에서 사용한다.

각 문자에 대해 자기 자신은 회문이므로 repeat[i][i]를 true로 초기화하고,

그 이후에 특정 구간이 회문인지 확인하기 위해

checkRepeat 메서드를 통해 회문 여부를 판별한다.

checkRepeat 메서드는 시작과 끝 문자가 동일한 경우,

해당 구간이 회문인지 확인하며 반복적으로 repeat 배열에 저장해 두고,

이후 구간이 회문임을 빠르게 참조할 수 있게 한다.

 

findRepeatGroup 메서드는 이 repeat 정보를 바탕으로 dp 배열을 갱신하는데,

각 문자 구간이 회문인지 확인하면서 최소 회문 분할 개수를 갱신한다.

만약 시작 인덱스가 0이라면 전체가 회문이므로 최소 개수인 1을 할당하고,

그렇지 않다면 현재 구간까지의 최소 회문 개수를 업데이트하여 구간별 최소값을 기록한다.

마지막으로 dp[len-1]에는 전체 문자열의 최소 회문 개수가 저장되어 출력되며,

이 값이 곧 전체 문자열을 회문으로 분할하는 데 필요한 최소 회문 개수이다.

 

 

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

public class Main {
    static int len;
    static boolean[][] repeat;
    static int dp[]; //첫 문자 ~ i 인덱스 번째 문자까지 회문 개수 최소값 저장
    static char[] charArr;

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

        charArr = br.readLine().toCharArray();
        len = charArr.length;
        repeat = new boolean[len][len];
        dp = new int[len];

        for(int i = 0; i < len; i++) {
            repeat[i][i] = true;
            for(int j = 0; j < i; j++)
                checkRepeat(j, i);
        }

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 1; //첫 문자 하나만 있는 경우
        if(dp[len-1]==1)
            System.out.println(1);
        else {
            findRepeatGroup(); //회문 최소 개수 찾기
            System.out.println(dp[len - 1]);
        }
    }

    public static void checkRepeat(int start, int end) {
        if(charArr[start] == charArr[end] && repeat[start + 1][end - 1])
            repeat[start][end] = true;
        if(charArr[start] == charArr[end] && repeat[start + 1][end])
            repeat[start][end] = true;
    }

    public static void findRepeatGroup() {
        for(int end = 0; end < len; end++) {
            for(int start = 0; start <= end; start++) {
                if(repeat[start][end]) {
                    if(start == 0) dp[end] = 1; //전체가 회문이므로 1개처리
                    else dp[end] = Math.min(dp[end], dp[start - 1] + 1);
                }
            }
        }
    }

}