[BOJ] 1509

팰린드롬 분할

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

분류

• Gold 1

• 다이나믹 프로그래밍

해법

BOJ_10942: 팰린드롬? 문제에서 최소 분할을 찾는 코드만 추가하면 됐습니다.

dp 배열을 adjacency matrix라고 생각해보면,
최소 분할은 bfs로 탐색할 수 있습니다.

정답 코드

/*
BOJ 1509: 팰린드롬 분할
*/

#include <bits/stdc++.h>
using namespace std;

string str;
int dp[2505][2505];
int depth[2505];

void sol1() {
    for (int i = 0; i < str.length(); i++) {
        dp[i][i] = 1;
    }
    for (int l = 2; l <= str.length(); l++) {
        for (int st = 0; st < str.length() - l + 1; st++) {
            int en = st + l - 1;
            if (str[st] != str[en]) continue;
            dp[st][en] = l == 2 || dp[st + 1][en - 1];
        }
    }
}

void sol2() {
    queue<int> q;
    depth[0] = 1;
    q.push(0);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur >= str.length()) {
            cout << depth[cur] - 1;
            return;
        }
        for (int i = cur; i < str.length(); i++) {
            if (dp[cur][i] == 0 || depth[i + 1]) continue;
            depth[i + 1] = depth[cur] + 1;
            q.push(i + 1);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> str;
    sol1();
    sol2();
    return 0;
}