팰린드롬? #10942

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력 1 복사

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 1 복사

1
0
1
1

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: bliss08, deneb2016, eric00513, tlsgkdns

알고리즘 분류

• 다이나믹 프로그래밍

시간 제한

• Java 8: 2.5 초
• PyPy3: 1.5 초
• Java 8 (OpenJDK): 2.5 초
• Java 11: 2.5 초
• PyPy2: 1.5 초
• Kotlin (JVM): 2.5 초

---

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

'''
1. 아이디어 :
    1) (시간초과) 들어오는 숫자를 chr로 바꾼 후 하나의 String을 만들어준다. [s-1:e]와 [s-1:e][::-1]을 비교한다.
    2) (시간초과) 문자열 슬라이싱에서 시간초과가 나는것 같다. 명령을 입력받기전에 미리 처리해놔야할것 같아서, 2차원 배열을 만들어서
    해당 인덱스의 숫자가 팰린드롬인지 아닌지를 저장한다.
    3)  저장하는 방식에서 시간초과가 나는 것 같다. 0~5까지의 문자열이 팔린드롬이면, 1~4, 2~3도 팔린들롬인걸 알 수 있다.
    2차원 배열을 Memoization 방식으로 채워야할것 같다.
2. 시간복잡도 :
    1) O(n) + O(m) * O(e-s) = O(max(n,m*(e-s)))
    - chr로 바꾼다 + 비교하는 입력 * 문자열 슬라이싱
    2) O(n) + O(m) * O(m-1) * O(e-s) = O(max(n,n^2*(e-s)))
    - chr로 바꾼다 + 인덱스마다 슬라이싱 한다
    3) O(n) + O(n) + O(n) * O(n) + O(m)= O(n^2)
    - 길이1 슬라이스 1로 만든다 + 길이2 팔렌드롬 체크 + 2차 배열을 채운다.*O(n^2) + 명령수
3. 자료구조 :
    1) 문자열
    2) 2차원 배열
    3) 2차월 배열
'''

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

# 2)
# n = int(input())
# nums = list(map(int, input().split()))
# chars = "".join([chr(num) for num in nums])
# pal_list = [[0] * n for _ in range(n)]
# for i in range(len(nums)):
#     for j in range(i, len(nums)):
#         if chars[i:j+1] == chars[i:j+1][::-1]:
#             pal_list[i][j] = 1
# for _ in range(int(input())):
#     s, e = map(int, input().split())
#     print(pal_list[s-1][e-1])




# 1)
# n = int(input())
# nums = list(map(chr, input().split()))
# chars = "".join([chr(num) for num in nums])
# for _ in range(int(input())):
#     s, e = map(int, input().split())
#     print(1 if chars[s-1:e] == chars[s-1:e][::-1] else 0)