[BOJ 1509] 팰린드롬 분할

BOJ 1509

문제

풀이

어떤 문자열을 부분 팰린드롬 문자열들로 분할했을 때 가장 길이가 작을 경우를 구해야한다.
길이 N의 문자열이 주어진다면, 길이가 1일 때부터 시작하여 다음 문자가 추가되었을 때의 최솟값을 구하면 된다.
이 때 문자가 하나 추가 될 때마다 해당 문자를 마지막으로 하는 팰린드롬을 만들 수 있는 경우들을 찾아 그 중 가장 작은 값을 최솟값으로 저장한다.

최대 길이가 2500으로 매 단어 추가 때마다 팰린드롬을 매번 확인할 수는 없으니 DP 배열을 선언하여 i번째 ~ j번째까지의 부분문자열이 팰린드롬이라면 DP[i][j]를 true로 저장하는 식으로 기억해둔다. 이러면 i ~ j의 문자열이 팰린드롬인지 확인할 때, DP[i + 1][j - 1]이 true인지 확인한 뒤, i번째와 j번째 문자가 동일한지만 확인하면 된다.

코드 (JavaScript)

function main() {
    const str = require('fs').readFileSync('input.txt').toString().trim();
    const N = str.length;
    const min = new Array(N).fill(0); // 길이가 N일 때의 분할 최솟값.
    const dp = new Array(N).fill(0).map(() => new Array(N).fill(false)); // i~j 문자열의 팰린드롬 여부
    min[0] = 1;

  	// 길이가 1인 문자열은 모두 팰린드롬이다.
    for (let i = 0; i < N; i++) {
        dp[i][i] = true;
    }

    for (let i = 1; i < N; i++) {
        const current = str[i]; // 새로 추가된 문자.
        const minTemp = []; // 팰린드롬을 만들 수 있는 경우의 최솟값들.
  
        if (current === str[i - 1]) {
            dp[i][i - 1] = true;

            minTemp.push(i >= 2 ? min[i - 2] + 1 : 1);
        }

        for (let j = i - 2; j >= 0; j--) {
            if (dp[i - 1][j + 1] && current === str[j]) {
                dp[i][j] = true;
                minTemp.push(j >= 1 ? min[j - 1] + 1 : 1);
            }
        }

  		// 팰린드롬을 만들 수 없는 경우 이전 길이의 최솟값 + 1이 된다.
        minTemp.push(min[i - 1] + 1); 
        min[i] = Math.min(...minTemp);
    }

    console.log(min[N - 1]);
}

main();