안녕하세요,
재재입니다.
BOJ 14517 팰린드롬 개수 구하기 Large 문제에 대한 풀이입니다.
BOJ 14517 팰린드롬 개수 구하기 Large
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/14517
관련 : https://www.acmicpc.net/problem/14505
(1000 이하) 길이의 문자열 S 가 주어진다.
‘abb’ 의 부분집합은 $$ a, b, b, ab, ab, bb, abb $$ 이고,
이 가운데 팰린드롬은 $$ a, b, b, bb $$ 으로 4개 입니다.
S의 부분집합 중 팰린드롬인 갯수를 구해주면 됩니다.
(2) 풀이 도출
문자열 S의 길이가 작다고 가정하면,
$$ O(n^4) $$ 의 풀이가 가능합니다.
상태공간은 다음과 같습니다.
dp[i][j] : i부터 j까지 남았을 때, 만들 수 있는 팰린드롬 (부분집합) 갯수
다음, 점화식은 아래와 같습니다.
$$ dp[i][j] = \Sigma dp[l][r] $$ 이고 조건은,
$$ S[l] = S[r] $$ 일 때, l 과 r 은 $ (i < l, r < j) $ 에 속합니다.
(관련문제 기준 S는 길이 30 이하)
(3) 풀이 도출
이제, S가 1000으로 늘어났으니 좀 더 빠른 방식이 필요합니다.
바로, 수학에서 포함 배제 원리를 활용하는 건데요.
포함 배제 원리에 따르면,
아래와 같은 식을 세울 수 있습니다.
$$ dp[i][j] = dp[l+1][r] + dp[l][r-1] + \alpha $$ 이고,
만약 (S[l] = S[r]) 일때 $$ \alpha = 1 $$
그 외에는 $$ \alpha = -dp[l+1][r-1] $$
이때, 시간 복잡도는 $$ O(S^2) $$ 입니다.