[백준][1509번][DP] 팰린드롬 분할

팰린드롬 분할

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

<코드>

#include <stdio.h>
#include <string>
using namespace std;
int Dp[2501][2501];
int result[2501];
int main(void){
 
    char room[2501];
    string size;
    int roomSize;
    scanf("%s", room);
    size = room;
    roomSize = size.size();
    
    for (int i = 1; i <= roomSize; i++)
        Dp[i][i] = 1;
    for (int i = 1; i <= roomSize-1; i++)
        if (room[i-1] == room[i])
            Dp[i][i + 1] = 1;
 
    for (int i = 2; i <= roomSize-1; i++)
        for (int j = 1; i+j <= roomSize; j++)
            if (room[j-1] == room[j + i-1] && Dp[j + 1][i + j - 1] == 1)
                Dp[j][i + j] = 1;
                
    for (int i = 1; i <= roomSize; i++){
        if ((result[i] != 0 && result[i] >result[i - 1] + 1) || result[i] == 0)
            result[i] = result[i - 1] + 1;
        
        for (int j = i + 1; j <= roomSize; j++){
            if (Dp[i][j] != 0)
            {
                if ((result[j] != 0 && result[j] >result[i-1] + 1) || result[j] == 0)
                    result[j] = result[i - 1] + 1;
            }
        }
 
    }
    printf("%d\n", result[roomSize]);
    return 0;
}

<문제 푼 요령>

1. 일단 Dp[i][j] i->j 까지가 펠린드 룸인지 판별하는 DP 테이블을 만든다.  만드는 방법은 이전글과 비슷하다.

2. 그 후 1~roomSize-1 까지 쭈욱 검사해서 여기서 펠린드 룸이 만들어 지는 경우가 있으면 그 뒤의 펠린드 룸이 만들어지는 지점에 result[i-1] +1 을 집어 넣어준다.

3. 이미 넣어진 값이 있으면 최소값을 비교해서 집어넣어준다.