[알고리즘/백준] 10942번 : 팰린드롬?(python)

처음에는 dp로 어떻게 풀어야하는지 막막했다.
여기서 팰린드롬의 경우의 수는 총 3가지 이다.
1. 길이가 1인 경우
2. 시작과 끝이 같고 가운데가 팰린드롬인 경우
3. 시작과 끝이 같고 길이가 2인경우

이렇게 세가지 경우에 관해서만 dp에 1을 추가해준다.

for문에서 조금 어려웠는데 무작정 오른쪽으로 진행하게 되면 풀리지 않는다.
dp[2][6]를 알기 위해서는 dp[3][5]가 팰린드롬인지 아닌지를 알아야하지만 오른쪽으로만 진행하게 되면 dp[3][5]는 비어있다.

따라서 대각선으로 탐색을 진행해야한다.

stdin을 안쓰면 시간초과..

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
M = int(input())
dp = [[0] * N for _ in range(N)]

for i in range(N):
    for s in range(N - i):
        e = i + s
        if e == s:
            dp[s][e] = 1
        elif a[s] == a[e]:
            if s + 1 == e:
                dp[s][e] = 1
            elif dp[s + 1][e - 1] == 1:
                dp[s][e] = 1

for _ in range(M):
    start, end = map(int, input().split())
    print(dp[start - 1][end - 1])