[문자열] 10942번: 팰린드롬? / 골드 3

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

10942번: 팰린드롬?

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

www.acmicpc.net

import sys
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

table = [[0]*n for _ in range(n)]
table[n-1][n-1] = 1

for i in range(n-1):
    table[i][i] = 1
    start = i
    end = i
    while end < n and start >= 0:
        if nums[start] == nums[end]:
            table[start][end] = 1
            start -= 1
            end += 1
        else:
            break

    if nums[i] != nums[i+1]:
        continue

    table[i][i+1] = 1
    start = i
    end = i+1
    while end < n and start >= 0:
        if nums[start] == nums[end]:
            table[start][end] = 1
            start -= 1
            end += 1
        else:
            break

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

시간 내에 통과하려면 dp로 접근해야 한다.