문제

자연수 $N$개로 구성된 배열이 있다.

시작지점 $S$와 끝 지점 $E$가 주어질 때, 두 지점을 포함한 구간의 자연수가 팰린드롬을 이루는지를 출력한다.

풀이

팰린드롬은 좌우대칭인 문자열이다. 임의의 팰린드롬을 $P$라고 가정하자. 만약 $P$ 좌우에 붙는 문자가 같은 문자라면, 새로운 팰린드롬 $xPx$ 역시 팰린드롬이라고 말할 수 있다.

즉, 범위가 주어질 때마다 해당 범위에서 앞뒤로 1씩 뺀 값이 팰린드롬인지 알 수 있다면, 새로이 팰린드롬인지 아닌지 확인하는 과정을 생략할 수 있다는 의미이다.

코드

# 팰린드롬?

import sys
input = sys.stdin.readline

len_nums = int(input()) # 수열의 크기
nums = list(map(int, input().split())) # 수열

dp = [[-1]*len_nums for _ in range(len_nums)] # dp[s][e] = S부터 E까지의 숫자가 팰린드롬을 이루는지

# 기본 단위 (길이가 1일 때, 2일 때) 

for i in range(0, len_nums-1):
    # 길이가 1일 때
    dp[i][i] = 1

    # 길이가 2일 때
    if nums[i] == nums[i+1]:
        dp[i][i+1] = 1
    else:
        dp[i][i+1] = 0
    
dp[-1][-1] = 1 # 맨 마지막 값은 i 범위에서 제외되므로

# DP

start_idx = 0
end_idx = 2
term = 2

while True:

    # 맨 끝을 잘랐을 때 팰린드롬인가?
    sub_prob = dp[start_idx+1][end_idx-1]

    #print("info:", start_idx, end_idx, sub_prob, nums[start_idx], nums[end_idx])

    if sub_prob == 1 and nums[start_idx] == nums[end_idx]:
        dp[start_idx][end_idx] = 1
    
    else:
        dp[start_idx][end_idx] = 0
    
    start_idx += 1
    end_idx += 1

    if end_idx >= len(nums):
        term += 1
        start_idx = 0
        end_idx = term

        if term >= len(nums):
            break

"""for row in dp:
    print(row)"""

num_q = int(input())

for _ in range(num_q):
    start_idx, end_idx = map(int, input().split())

    # 1-base index므로 재조정
    print(dp[start_idx-1][end_idx-1])