팰린드롬?

🤔 접근

빡구현 한다면 시간 초과가 날 것이 뻔하기 때문에 중복되는 연산을 메모리에 저장해두는 dp를 활용하였다.
각 숫자 간의 관계를 저장할 수 있는 n * n 테이블을 선언하고, 숫자 간의 간격이 작은 순으로 저장을 해준다면 다음과 같은 방식으로 처리할 수 있다.

dp를 활용하기 위해서는 글자수가 작은 수열관계부터 dp에 저장해 나가야 한다.

1. 1글자라면 팰린드롬 수다.
2. 2글자라면, 첫 글자와 끝 글자가 같다면 팰린드롬 수다.
3. 3글자 이상이라면, 첫 글자와 끝 글자가 같고, 두번째와 마지막에서 두번째까지의 수가 팰린드롬이라면 팰린드롬수다.

💻 코드

#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(0, n): # 간격 설정
    for start in range(1, n+1-i):
        end = start + i 
        if start == end : # 1글자
            dp[start][end] = 1 
        elif arr[start] == arr[end] : 
            if start + 1 == end: # 2글자
                dp[start][end] = 1 
            elif dp[start+1][end-1] == 1: #3글자 이상
                dp[start][end] = 1 


m = int(input())
for _ in range(m):
    s, e = map(int, input().split())
    print(dp[s][e])