[알고리즘 문제 풀기] 팰린드롬 분할(1509)

1. 문제 풀이 아이디어

• 문자열의 부분 문자열 중 팰린드롬인 구간을 미리 계산해 두고, 그 정보를 바탕으로 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string line = sr.ReadLine();
    bool[,] p = new bool[line.Length, line.Length];
    for (int i = 0; i < line.Length; i++) p[i, i] = true;
    for (int i = 0; i < line.Length - 1; i++)
    {
        if (line[i] == line[i + 1]) p[i, i + 1] = true;
    }
    for (int i = 2; i < line.Length; i++)
    {
        for (int j = 0; j < line.Length - i; j++)
        {
            if (line[j] == line[j + i] && p[j + 1, j + i - 1]) p[j, j + i] = true;
        }
    }
    int[] dp = new int[line.Length + 1];
    for (int i = 1; i <= line.Length; i++)
    {
        dp[i] = int.MaxValue;
        for (int j = 1; j <= i; j++)
        {
            if (p[j - 1, i - 1]) dp[i] = Math.Min(dp[j - 1] + 1, dp[i]);
        }
    }
    sw.WriteLine(dp[line.Length]);
}

3. 정리

• p[i, j]는 line[i..j]가 팰린드롬인지 여부를 저장한다.

• 길이 1은 항상 true, 길이 2는 두 문자가 같을 때 true로 초기화한다.

• 길이 3 이상은 양 끝이 같고, 안쪽이 팰린드롬일 경우 true로 설정한다.

• dp[i]는 line[0..i-1]까지 최소로 나누는 팰린드롬 개수를 저장한다.

• dp[i]는 j를 1부터 i까지 순회하며 line[j-1..i-1]가 팰린드롬이면 dp[i] = min(dp[i], dp[j-1] + 1)로 갱신한다.

• 최종적으로 dp[line.Length]를 출력하여 문제를 해결한다.