백준 10942 팰린드롬?

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

이 문제를 완전탐색으로 계산한다면 배열의 절반만큼 M개의 질문을 연산하면 대략 10억의 연산이 나오기 때문에 시간초과가 자명하다.

그렇다면 중복을 줄일 수 있는 방법을 찾아야 하는데, 가장 먼저 떠오르는 중복은
예를 들어 내가 1~7까지가 팰린드롬이란걸 알고있다면 2~6도 팰린드롬이고, 3~5도 팰린드롬이다.
위의 예를 일반화해서 말하면 s~e까지가 팰린드롬이라면 s+1~e-1까지도 팰린드롬이란 것이다.

dp는 i번부터 시작해 j번까지 팰린드롬인지 아닌지를 기록해 놓는 배열이다.
대각 뿐만아니라 대각 옆에 있는 수가 팰린드롬인지 아닌지도 체크를 해주어야 한다.

그렇기 때문에 s를 최대한 오른쪽으로 붙이고 점점 왼쪽으로 넓혀나가는 식으로 dp를 해야한다.

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
m = int(input())
dp = [[0]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 1
for i in range(n-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = 1
for i in range(n-1,-1,-1):
    for j in range(i+2,n,1):
        if arr[i] == arr[j] and dp[i+1][j-1]:
            dp[i][j] = 1
for i in range(m):
    s,e = map(int,input().split())
    s -= 1; e -= 1;
    print(dp[s][e])