[백준] 1509번 - 팰린드롬 분할 (Java)

문제

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

1509번: 팰린드롬 분할

 

입력

 

출력

---

알고리즘

다이나믹 프로그래밍

 

주어진 문자열이 어디부터 어디까지가 팰린드롬인지 미리 기록을 해두고, 이를 이용해 팰린드롬 분할의 개수 최솟값을 갱신한다.

 

우선, 어디부터 어디까지가 팰린드롬인지 기록할 DP 테이블을 하나 만들어야한다.

palandrom[i][j] : 문자열의 i번째 부터 j번째 까지가 팰린드롬인가? (true면 팰린드롬)

 

위와 같이 초기값을 우선 갱신해둔다. (자기자신과 하나 차이날 경우 인덱스 관리를 위해서 미리 기록해두는 것이다.) 그 다음, 문자열의 왼쪽 끝을 가르킬 j포인터와 오른쪽 끝을 가르킬 i 포인터를 만든다. 부분 문자열이 있을때, 그 문자열의 왼쪽 끝과 오른쪽 끝이 같고, 그 둘 사이 중간이 팰린드롬이라면 그 부분 문자열이 팰린드롬이 된다.

 

예시로 3가지 문자열의 경우를 들어보겠다.

1. ABCBA는 팰린드롬인가?

→ 문자열의 맨 왼쪽 끝과 맨 오른쪽 끝은 A와 A로 같다. 그리고 그 중간에 있는 값 BCB는 팰린드롬이다. 따라서 palandrom[1][3] = true라고 그 전에 기록이 되어있을 것이다. 맨 왼쪽 끝과 오른쪽 끝이 같고 그 사이 중간 문자열이 팰린드롬이므로, ABCBA는 팰린드롬이 되어 palandrom[0][4] = true로 기록이 될 것이다.

2. ABCBB는 팰린드롬인가?

→ 문자열의 맨 왼쪽 끝과 맨 오른쪽이 A와 B로 같지 않으므로 팰린드롬이 아니다. 따라서, palandrom[0][4] = false로 기록될 것이다.

3. ACABA는 팰린드롬인가?

→ 문자열의 맨 왼쪽 끝과 맨 오른쪽 끝은 A와 A로 같다. 하지만 그 중간에 있는 값 CAB는 팰린드롬이 아니다. 즉, palandrom[1][3] = false라고 기록이 되어있을 것이고, palandrom[0][4] = false로 기록될 것이다.

 

위와 같은 과정으로 팰린드롬 확인 여부를 미리 다 기록을 해둔다.

 

 

dp[i] : 문자열의 i번째까지 봤을때 팰린드롬 분할 개수의 최솟값

우선, 팰린드롬 분할 개수의 최댓값은 문자열의 길이랑 동일하다. 우리는 최솟값을 계속 갱신해야 되기 때문에 사전에 최댓값으로 미리 초기값을 설정해준다. 그 다음, 아까 기록한 팰린드롬 여부로 이제 팰린드롬 분할 최솟값을 갱신시킨다. 만약에 j번째부터 i번째까지가 팰린드롬이다? 그럼 j번째부터 i번째까지의 팰린드롬이 하나 추가되므로 분할 개수가 1개 추가되는 것이다. 따라서 0번째부터 (j-1)번째 까지의 팰린드롬 분할 최소 개수에 1개를 추가해주면 된다. 그리고 이걸 이제 비교해서 더 작은 값으로 갱신시켜준다.

 

위와 같은 과정으로 반복문을 돌린 후, 문자열의 최종 길이에서의 팰린드롬 분할 개수 최댓값을 출력해주면 답이된다.

---

코드

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

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

        int[] dp = new int[origin.length()+1];
        makeTable(origin);
        
        //dp[i] : 문자열의 i번째 자리까지 봤을때 팰린드롬 분할의 최솟값
        for(int i = 1; i<=origin.length(); i++){
            dp[i] = origin.length(); //최댓값으로 초기값 갱신
            for(int j = 1; j<=i; j++){
                //j~i문자열까지가 팰린드롬이니깐 팰린드롬 분할 개수가 1개가 추가된다.
                //j~i까지가 팰린드롬이니깐, 0~j-1번째까지 팰린드롬 분할 개수의 최솟값에서 새로 들어온 팰린드롬 1개를 추가시킨다.
                //두개중 더 작은 값으로 갱신시켜버린다.
                if(palandrom[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
            }
        }

        System.out.println(dp[origin.length()]);
    }
    
    //팰린드롬 확인용 테이블 만들기
    public static void makeTable(String T){
        //palandrom[i][j] : i번째부터 j번째 문자열까지가 팰린드롬인가? (true면 팰린드롬)
        palandrom = new boolean[T.length()+1][T.length()+1];
        
        //초기값 갱신
        for(int i = 1; i<=T.length(); i++) palandrom[i][i] = true;
        for(int i = 1; i<T.length(); i++) if(T.charAt(i-1) == T.charAt(i))palandrom[i][i+1] = true;

        for(int i = 2; i<=T.length(); i++){
            for(int j = 1; j<i; j++){
                //맨 왼쪽끝과 맨 오른쪽 끝이 같고 그 사이 중간값들이 팰린드롬이면 무조건 팰린드롬
                if(T.charAt(j-1) == T.charAt(i-1) && palandrom[j+1][i-1]){
                    palandrom[j][i] = true;
                }
            }
        }
    }
}

---

참고

 

백준 2079번 - 팰린드롬과 완전히 동일한 문제입니다.

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

2079번: 팰린드롬