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

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

14517번: 팰린드롬 개수 구하기 (Large)

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:43:46

 

---

 

문제 설명

 

 

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

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

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

abb

 

출력 예시

 

4

 

 

---

 

풀이

 

DP 문제. DP 문제는 항상 내게 겸손함을 불어넣어준다 :)

 

[a, b] 구간의 팰린드롬의 개수를 dp[a][b]라고 두자. 그렇다면, 점화식으로 dp[a][b] = dp[a+1][b] + dp[a][b-1] 으로 대충 유도할 수 있다. 문제는 이 dp[a+1][b]와 dp[a][b-1]가 공통적으로 dp[a+1][b-1]을 보유하고 있다는 점이다.

 

즉 포함 배제의 원리를 적용하여 dp[a+1][b-1]을 제거해야 한다. 따라서  dp[a][b] = dp[a+1][b] + dp[a][b-1] - dp[a+1][b-1] 가 성립한다.

 

그리고 S[a] == S[b]인 경우 역시 고려하자. 이 경우는 두 가지, 즉

 

• S[a]S[b] 그 자체
• S[a] + (dp[a+1][b-1] 에 속한 팰린드롬들) + S[b]

 

경우가 추가로 팰린드롬의 조건을 만족한다. 따라서 이 경우 추가로 dp[a][b] += dp[a+1][b-1] + 1 을 더해주어야 한다.

 

풀이 코드

MOD = 10007
S = input().strip()
N = len(S)
dp = [[0]*N for _ in range(N)]
for i in range(N) :
  dp[i][i] = 1
for i in range(1, N) :
  for j in range(N-i) :
    dp[j][j+i] = (dp[j][j+i-1] + dp[j+1][j+i] - dp[j+1][j+i-1]) % MOD
    if S[j] == S[j+i] :
      dp[j][j+i] = (dp[j][j+i] + dp[j+1][j+i-1] + 1) % MOD
print(dp[0][-1])

풀이 완료!