[백준] 10942번 펠린드롬 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/10942

문제해결 아이디어

• 양 끝의 문자가 다르면 -> 팰린드롬 아님
• 양 끝의 문자가 같을 때, 가운데 문자열이
  • 팰린드롬이라면 -> 팰린드롬
  • 팰린드롬이 아니라면 -> 팰린드롬 아님
  • 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다.

소스코드

import sys

input = sys.stdin.readline

n = int(input())

arr = [0] + list(map(int, input().split()))

dp = [[0]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    dp[i][i] = 1

for i in range(1, n):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = 1

for i in range(1,n-1):
    for j in range(i+2, n+1):
        if arr[i] == arr[j]:
            dp[i][j] = dp[i+1][j-1]

for i in range(3,n+1):
    for j in range(1, n+1-i):
        if arr[j] == arr[i+j]:
            dp[j][i+j] = dp[j+1][i+j-1]



for _ in range(int(input())):
  a,b = map(int, input().split())
  print(dp[a][b])