BOJ 1509. 펠린드롬

BOJ 1509. 펠린드롬

랭크 : 골드1

문제 풀이

외판원 순환 문제에서 사용한 dp처럼 끝에 부분부터 최소값을 확정해나가면 밑에서의 분기점을 많이 없앨 수 있습니다. 여기에 펠린드롬 구역을 미리 계산해두어, 이를 바로 사용할 수 있도록 하였습니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

vector<vector<int>> board(2501, vector<int>());
int minboard[2501];
int len;

int dfs(int step, int total) {
    if (step == len) return 1;
    if (minboard[step] != 0) return minboard[step];
    minboard[step] = 2501;
    for (auto num : board[step]) minboard[step] = min(minboard[step], dfs(num + 1, total) + 1);
    return minboard[step];
}

int main() {
    fastio;
    std::string str;
    cin >> str;
    len = str.size();

    for (int i=0; i < len; i++) {
        int x = i;
        int y = i;
        while (x >= 0 && y < len) {
            if (str[x] != str[y]) break;
            board[x].push_back(y);
            x--; y++;
        }
        x = i;
        y = i + 1;
        while (x >= 0 && y < len) {
            if (str[x] != str[y]) break;
            board[x].push_back(y);
            x--; y++;
        }
    }
    cout << dfs(0, 0) - 1<< endl;
}

알고리즘	시간복잡도	공간복잡도
DP	$O(N^2)$	$O(N^2)$