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

문제

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

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

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

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

입력

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

출력

주어진 문자열 S 의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 출력한다.

---

풀이

모든 부분 수열의 펠린드롬을 세어야 한다.

두 가지 방법이 있다.

비재귀 풀이

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

 

재귀 풀이

앞선 비재귀 풀이 방식보다는 좀 더 직관적인 풀이 방식이다.

2차원 배열을 사용하는 방법이다.

dp[i][j] : 문자열의 i ~ j 구간에서 발견된 모든 펠린드롬 수

만약 L과 R이 같다면 길이가 1인 문자로 자기 자신이 펠린드롬이 된다. 1을 반환하자.

이전에 이미 구한 작은 펠린드롬이라면 미리 계산한 값을 반환하면 된다.

마찬 가지로 완전 탐색을 하며 부분 수열이 펠린드롬인 경우를 찾았고, 길이가 3이상이라면

자신보다 작은 부분 수열 펠린드롬을 탐색하는 방법이다.

---

소스코드

보기

---

출처

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