백준 1509 펠린드롬 분할 java

전수민

Dec 7, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

2. 코드가 나오기까지 🛠️

(1) 펠린드롬이 될 수 있는 수 체크

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/1509
세준이가 주어진 문자열을 최소개수의 펠린드롬으로 분할하려고 한다.
이때 최소 개수가 몇인지 출력하라.

2. 코드가 나오기까지 🛠️

KEY WORD: DP

(1) 펠린드롬이 될 수 있는 수 체크

단일 문자는 무조건 펠린드롬임.
더해서 똑같은 문자가 두 개인 경우도 펠린드롬에 해당

세 번째부터가 문제인데, 이때는 맨 끝 (오른쪽, 왼쪽)이 같은 수이고, 안의 값이 펠린드롬이면, 펠린드롬 수임.

안의 값이 펠린드롬인지는 DP로 기억했다가 긴가 아닌가 맞춰보면 된다.

(2) DP 세팅

2차원 boolean 배열 palindromes [ ] [ ] 를 만든다.
palindromes [i] [j] 는 문자열에서 i부터 j까지 범위만 봤을 떄, 펠린드롬 수이면 true, 아니면 false를 반환한다. 범위가 1인 경우, 2인 경우부터 시작해서 늘려가면, 모든 범위에 대하여 펠린드롬인지 확인이 된다.

문제에 설명된 ABACABA에 대해서 해보면 다음과 같이 된다.

코드로 나타내면 다음과 같다.


for(int i = 0; i < row.length(); i++){
    palindromes[i][i] = true;
    if(0 < i && row.charAt(i-1) == row.charAt(i)) palindromes[i-1][i] = true;
    for(int j = 0; j < i; j++){
        if(row.charAt(j) == row.charAt(i) && palindromes[j+1][i-1]) palindromes[j][i] = true;
      }
}

(3) 최소 펠린드롬 수 구하기

최소 펠린드롬을 구하기 위한 1차원 int 배열 dp [] 을 만든다.
dp [i] 의 값은 0 ~ i 까지 확인했을 때 최소 펠린드롬 수 이다.

A. 초기화

하나의 문자열에서 나올 수 있는 최대 펠린드롬 수는 모든 문자를 분할하는 것이다. 따라서 문자열의 길이가 곧 최대 펠린드롬 수이다.

B. 값 계산: 투 포인터 운용

아까 구했던 palindromes 배열에서 투 포인터를 운용해 최소 펠린드롬 수를 구한다.
만약 palindromes [j] [i]가 true 즉, 펠린드롬 수이면, dp[i]의 값은 dp[j-1] (j-1 번까지 계산했을 때 최소 펠린드롬 수) + 1 될 수 있다. 0 ~ i 까지의 범위 내에 이러한 경우의 수를 모두 구하여 그 중 최소값을 dp[i] 에 저장하면 된다.

코드로 나타내면 다음과 같다.


        for(int i = 0; i < dp.length; i++){
            dp[i] = dp.length;
            if(palindromes[0][i]) dp[i] = 1;
            for(int j = 1; j <= i; j++){
                if(palindromes[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
            }
        }

(1) 시간복잡도 분석 ⏳

2차원 문자열을 만드는 것이 최대 시간 복잡도이다 . 따라서 $O(n^{2})$ 이다. n은 최대 2,500이라서 가뿐히 통과한다.

3. 코드 🌐


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

public class Main {
    static boolean [][] palindromes;
    static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String row = br.readLine();
        palindromes = new boolean[row.length()][row.length()];
        dp = new int [row.length()];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int i = 0; i < row.length(); i++){
            palindromes[i][i] = true;
            if(0 < i && row.charAt(i-1) == row.charAt(i)) palindromes[i-1][i] = true;
            for(int j = 0; j < i; j++){
                if(row.charAt(j) == row.charAt(i) && palindromes[j+1][i-1]) palindromes[j][i] = true;
            }
        }
        for(int i = 0; i < dp.length; i++){
            dp[i] = dp.length;
            if(palindromes[0][i]) dp[i] = 1;
            for(int j = 1; j <= i; j++){
                if(palindromes[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
            }
        }
        System.out.println(dp[dp.length-1]);
    }
}