[Python] 백준 10942: 팰린드롬?

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

10942번: 팰린드롬?

1. m <= 1000000 로 들어오므로 입력을 sys.stdin.readline 으로 받아야 한다.

2. 시작과 끝이 같을 때 무조건 가능하고, 시작과 끝의 자릿수가 1자리 차이날때는 수가 같아야한다.

3. 시작과끝의 갭이 3이상일때부터는 바로 전의 자리가 팰린드롬 이여야 하고 현재 시작과 끝의 수가 같아야한다. 

예를들면 1 2 4 2 1 이라는 수가 있다고 가정하면 1 2 4 2 1  2 4 2가 팰린드롬이여야하고 1과 1이 같아야 성립한다.

import sys

n = int(input())
a = [0] + list(map(int, sys.stdin.readline().split()))
m = int(input())
dy = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
    dy[i][i] = 1

for i in range(1, n):
    dy[i][i+1] = 1 if a[i+1] == a[i] else 0

for j in range(2, n):
    for i in range(n-j+1):
        k = j+i
        if dy[i+1][k-1] and a[i] == a[k]:
            dy[i][k] = 1
        else:
            dy[i][k] = 0

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(dy[s][e])