Algorithm/DP

BOJ#1509 팰린드롬 분할

밤이2209 2017. 10. 27. 01:06

BOJ#1509 팰린드롬 분할


* 문제



* 풀이

- Manacher 알고리즘을 통해 임의의 범위의 문자열이 팰린드롬인지 구한다.

- dp[i] : 0 ~ i 범위의 문자열을 팰린드롬 분할할 때 최소 분할 수

j ~ i 범위 문자열이 팰린드롬일 때, dp[i] = min(dp[i], dp[j-1] + 1)
(여기서 j는 0 부터 i 까지)

dp[0] = 1이고 -> dp[1] -> dp[2] -> ... -> dp[N-1]을 차례대로 구한다


* 나의 코드

https://github.com/stack07142/BOJ/blob/d4b527b666ba54f7f53c1128f5a1523cb261d2b9/BOJ%231509/src/Main.java


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

// Input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();

int N = input.length() * 2 - 1;

char[] S = new char[N];

int idx = 0;
for (int i = 0; i < N; i += 2) {

S[i] = input.charAt(idx++);
}

int[] A = new int[N];

// Solve

int[] dp = new int[N];

dp[0] = 1;

manacher(S, A, N);

for (int i = 2; i < N; i += 2) {

dp[i] = N;
for (int j = 0; j <= i; j += 2) {

int center = (i + j) / 2;
int radius = (i - j) / 2;

if (A[center] >= radius) {

dp[i] = Math.min(dp[i], j - 1 >= 0 ? dp[j - 2] + 1 : 1);
}
}
}

System.out.println(dp[N - 1]);
}

static void manacher(char[] S, int[] A, int N) {

int R = -1;
int p = -1;

for (int i = 0; i < N; i++) {

// A[i]의 초기값 설정
if (R < i) A[i] = 0;
else A[i] = Math.min(R - i, A[2 * p - i]);

// i를 기준으로 양 옆으로 범위를 넓혀가면서 검사
while ((i - A[i] - 1 >= 0) && (i + A[i] + 1 < N)
&& (S[i - A[i] - 1] == S[i + A[i] + 1])) {

A[i]++;
}

// R과 p를 갱신
if (i + A[i] > R) {

R = i + A[i];
p = i;
}
}
}
}


'Algorithm > DP' 카테고리의 다른 글

BOJ#1003 피보나치 함수  (1) 2018.05.28
BOJ#11049 행렬 곱셈 순서  (3) 2017.10.27
BOJ#2352 반도체 설계  (0) 2017.10.09
BOJ#1495 기타리스트  (0) 2017.10.09
BOJ#2631 줄세우기  (0) 2017.09.28