[JAVA] 백준 1509 팰린드롬 분할

 

DP 개념이 2개나 들어간 쉽지 않은 문제다..

 

분할의 개수의 최솟값을 구하기 위해서는 모든 구간을 다 탐색하면서 펠린드롬인지 아닌지를 확인해야한다.

pal[i][j[는 i~j 구간이 펠린드롬인지 여부를 저장하는 배열이다.

 

pal[i[j]를 구할때 DP 없이 그냥 풀면 O(n^3)이 나온다 이렇게 해도 운이 좋았는지 Pass는 되었다.

모든 구간을 탐색하는 코드이다.

for(int i =0; i<n; i++){
            for(int j =i; j<n; j ++){
                int from = i;
                int to = j;
                boolean result = true;
                while(from <= to){
                    if(s.charAt(from) != s.charAt(to)){
                        result = false;
                        break;
                    }
                    from +=1;
                    to -=1;
                }
                if(result){
                    pal[i][j] = true;
                }

            }
        }

 

이를 개선하기 위해 DP를 사용하는데

모든 길이가 1인 문자는 펠린드롬, 뒤와 같은 값을 가진 구간은 펠린드롬일 것이고

구간 i~j가 만약 펠린드롬이라면 i-1의 문자열과 j+1의 문자열이 같다면 i-1~j+1도 펠린드롬일 것이다.

이 개념을 통해 DP를 구현한다.

for(int i=0; i<n; i++){
            pal[i][i] = true;
        }
        for(int i=0; i<n-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){
                pal[i][i+1] = true;
            }
        }
        
        for(int i =2; i<n; i++){
            for(int j =0; i+j <n; j++){
                if(s.charAt(j) == s.charAt(i+j) && pal[j+1][i+j-1]){
                    pal[j][i+j] = true;
                }
            }
        }

구간의 길이가 3인것 구간의 길이가 4인것 증가하면서 확인하는 코드이다.

i가 구간길이를 나타내며 j는 iterator라고 보면 된다.

 

이렇게하면 pal 배열에 구간별 펠린드롬 여부가 저장되었을 것이고 

이제 모든 구간에 대해 최솟값을 찾아야한다.

 

구간에 대해 동적으로 업데이트하기 위해선

i~j의 구간이 만약 펠린드롬이라면 이러한 점화식으로 계산하면 된다.

Math.min(dp[i-1] +1, dp[j])  

은근히 직관적이다. 

dp[j]의 의미는 j까지 구간의 최소 펠른드롬 개수고 

dp[i-1]+1의 의미는 i이전까지의 펠린드롬개수 + i~j 구간의 펠린드롬이기 떄문이다

 

// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String s = br.readLine();
        
        int n = s.length();
        
        boolean[][] pal = new boolean[n][n];
        
        for(int i=0; i<n; i++){
            pal[i][i] = true;
        }
        for(int i=0; i<n-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){
                pal[i][i+1] = true;
            }
        }
        
        for(int i =2; i<n; i++){
            for(int j =0; i+j <n; j++){
                if(s.charAt(j) == s.charAt(i+j) && pal[j+1][i+j-1]){
                    pal[j][i+j] = true;
                }
            }
        }
        
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i= 1; i<=n; i++){
            for(int j = i; j<=n; j++){
                if(pal[i-1][j-1]){
                    dp[j] = Math.min(dp[i-1] +1, dp[j]);
                }
            }
        }
        bw.write(dp[n] + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

구간의 펠린드롬 여부를 확인할떄 DP사용여부에 따라 시간 차이가 많이 나는걸 확인할 수 있따.