[백준] 10942 팰린드롬?(python)

문제

문제 설명

• 숫자 리스트와 시작 인덱스 S, 끝 인덱스 E가 주어진다.
• 리스트의 S번째 원소에서 E번째까지의 원소가 팰린드롬인지 여부를 반환하는 문제이다.

풀이

• 리스트가 주어졌을 때 2차원 dp로 팰린드롬의 여부를 저장한 뒤, 인덱스 값에 따른 결과를 출력

import sys


input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
M = int(input())

dp = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    dp[i][i] = 1

for i in range(N - 1, -1, -1):
    for j in range(i + 1, N):
        if lst[i] == lst[j]:
            if j - i == 1:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i + 1][j - 1]

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