PS/Baekjoon Online Judge

[백준 14517] 팰린드롬 개수 구하기 (Large) [Python]

kimyoungrok 2024. 9. 18. 18:10
728x90

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.

승수는 주어진 문자열의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 알고싶어한다. (공집합은 포함하지 않는다)

예를들어 'abb' 의 부분수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb'} 이고 이 가운데 팰린드롬은 {'a'}, {'b'}, {'b'}, {'bb'} 으로 4개 이다. 

문자열이 주어졌을 때, 팰린드롬이 되는 부분수열의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 길이가 1000을 넘지 않는 문자열 S 가 주어진다. 문자열 S는 알파벳 소문자로만 이루어져 있다.

출력

주어진 문자열 S 의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 10,007 로 나눈 나머지를 출력한다.


풀이

이전에 푼 문제의 확장판이다.

2024.09.18 - [PS/Baekjoon Online Judge] - [백준 14505] 팰린드롬 개수 구하기(Small) [Python]

 

[백준 14505] 팰린드롬 개수 구하기(Small) [Python]

문제팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.승수는

kyr-db.tistory.com

 

부분 수열 펠린드롬을 구하기 위해서는 이전에 사용했던 O(N^3)방식을 쉽게 떠올릴 수 있다.

하지만, 이번에는 N이 1000으로 같은 방식을 사용하면 시간 초과가 발생한다.

때문에 더 빠른 방법을 찾아야 한다.

 

문제의 풀이 아이디어는 다음과 같다.

O(N^2)탐색은 필수적이고, 현재 i ~ j구간에서 발견한 부분 수열 펠린드롬의 수는, i + 1 ~ j 구간에서 발견한 부분 수열 펠린드롬들의 부모 펠린드롬이다.

 

dp[i] : i번째에서 새로 발견된 회문 수와 현재 검사하는 문자열 보다 긴 문자열의 펠린드롬 수

prefix_sum_dp[i] : 1 ~ i번째 문자에 대해 발견된 펠린드롬 수

반복문을 돌며 부분 수열 펠린드롬을 찾고(+1), 이전 단계에서 찾은(부모 펠린드롬의 수) 누적합 펠린드롬 (prefix_sum_dp[N] - prefix_sum_dp[r])을 더해주자.

i = 1일때는 무시된다.

문자열 "ababa"에 대해 

i = 1, j = 5일 때, 발견한 펠린드롬은 {"a", "a_a", "a___a"}이다.

i = 2일 때부터 누적합을 이용한다.

i = 2, j = 2일 때 이전에 발견한 펠린드롬을 활용해 만들어지는 펠린드롬은 {"a", "b", "aba", "ab__a"}가 된다.

하지만, 이 때 prefix_sum_dp[N]을 전부 더하면 prefix_sum_dp[r]을 갱신하는 과정에서 중복되는 펠린드롬이 발생한다.

때문에, dp[r] + prefix_sum_dp[N] 다음 prefix_sum_dp[r]을 빼고, prefix_sum_dp[r]을 갱신할 때, dp와 prefix_sum_dp[r - 1]을 더해주어 prefix_sum_dp에 올바른 누적합이 저장되도록 한다.


소스코드

보기


출처

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

728x90