Baekjoon 14517. 팰린드롬 개수 구하기 (Large) / Python

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

알고리즘 설명

1. DP 배열 채우기:
   • 길이 2 이상인 부분 문자열에 대해 DP 배열을 채운다.
   • dp[j][j + i]는 dp[j][j + i - 1]와 dp[j + 1][j + i]의 합에서 dp[j + 1][j + i - 1]을 뺀 값
   • 만약 s[j] == s[j + i]이면, dp[j][j + i]에 dp[j + 1][j + i - 1] + 1을 더한다
2. 결과 출력:
   • dp[0][n-1] 값 = 전체 문자열에서 팰린드롬 부분수열의 개수

s = input()

# 문자열 길이
n = len(s)

# DP 
dp = [[0] * n for _ in range(n)]

# 결과를 10007로 나눌 것이므로 이를 상수로 설정
div = 10007

# 길이가 1인 모든 부분 문자열은 팰린드롬이므로 1로 초기화
for i in range(n):
    dp[i][i] = 1

# 길이가 2 이상인 부분 문자열에 대해 DP 배열 채우기
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]) % div
        
        # s[j]와 s[j + i]가 같은 경우 추가 계산
        if s[j] == s[j + i]:
            dp[j][j + i] = (dp[j][j + i] + dp[j + 1][j + i - 1] + 1) % div

# 최종 결과 출력: 전체 문자열의 팰린드롬 부분수열의 개수
print(dp[0][n - 1])