BOJ 10942 팰린드롬?

https://www.acmicpc.net/problem/10942
시간 0.5초, 메모리 256MB
input :

• N (1 ≤ N ≤ 2,000)
• 칠판에 적은 수는 100,000보다 작거나 같은 자연수
• M (1 ≤ M ≤ 1,000,000)
• S와 E가 한 줄에 하나씩 입력 됨.

output :

• 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력

조건 :

• 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

---

dp[start][end] 에다가 팰린드롬의 결과를 저장해놓도록 ㅎ자ㅏ.

그런데 이거를 처음부터 팰린드롬을 찾듯이 해버리면 시간초과가 발생한다.
생각해보면 dp를 이용하는게 저런거 안 하려고 쓰는 건데 ... 음 생각이 없었나 보다.
암튼 길이가 1, 2인 경우엔는 dp[start][end] = 1로 업데이트를 해두고 그 이상의 길이에서는 제일 앞, 뒤만 확인 한 이후에 dp[start + 1][end - 1]을 확인해서 팰린드롬인지 확인하자.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [[0] * n for i in range(n)]

for b in range(n):
    for start in range(n):
        end = start + b

        #그냥 구간을 따지자. 어차피 다 돌면서 하면 시간 초과 난다.
        if end >= n:
            break

        if start == end:
            dp[start][end] = 1
            continue

        if start + 1 == end:
            if data[start] == data[end]:
                dp[start][end] = 1
                continue

        #제일 앞 뒤만 같은 지 확인 하고 그 이외의 것은 다른 dp에 저장된 값을 가지고 오자.
        if data[start] == data[end] and dp[start + 1][end - 1]:
            dp[start][end] = 1

m = int(sys.stdin.readline())
for i in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(dp[s - 1][e - 1])