[백준 10942번] 팰린드롬? (Python3)

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int,input().split()))
M = int(input())

Q = []
for i in range(M):
  start,end = map(int,input().split())
  Q.append((start-1,end-1))

palin = [1]*(2*N-1)

for x,y in Q:
  answer = 1
  center = x+y
  gap = y-x+1
  if palin[center] >= gap:
    print(1)
  else:
    while True:
      if x>=y:
        palin[center] = gap
        print(1)
        break
      if num[x] != num[y]:
        print(0)
        break
      x+=1
      y-=1

중심점을 기준으로 한 DP리스트를 만들어 중심점을 기준으로 몇 거리까지가 팰린드롬인지를 기록한 뒤, Q의 질문이 DP리스트에 포함되면 답을 불러오고, 그렇지 않으면 계산하는 방식을 이용하였다.

 

pypy3로는 잘 통과가 되었는데 python3로는 통과가 되지 않았다. 시간복잡도를 줄일 수 있는 방법을 좀더 모색해야겠다.

 

 

오늘의 교훈) 시간복잡도를 줄이자