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

백준 10942 팰린드롬?

DP를 활용하여 풀었을 때, 최악의 경우를 계산해 보면 $2 \sum^{1000}_{n = 1}(n) + 1,000,000$ 즉, 대략 2,000,000으로 시간 초과에 걸리지 않을 수 있다는 것을 알 수 있다. 문제의 포인트는 다음과 같다.

1. 각 인덱스가 중점일 때, 어디까지가 팰린드롬인지 dp에 저장한다. 단, 두 가지 경우가 있음에 유의하자.
   • 총 길이가 홀수인 경우에 중앙 값은 하나.
   • 총 길이가 짝수인 경우에 중앙 값은 둘. (더 작은 인덱스로 통일)
2. dp 리스트에서 각 인덱스에 저장할 값은 두 개다(길이가 홀수인 경우, 짝수인 경우)
3. 비교 값을 받았을 경우 dp를 활용해 팰린드롬인지 확인하여 출력한다.

import sys

input = sys.stdin.readline

n = int(input().strip())
nList = list(map(int, input().split()))
dp = [[i for _ in range(2)] for i in range(n + 1)]

p = 0
while p < n:
    # case 1 -> 간격이 홀수
    lp = p - 1
    rp = p + 1
    while lp >= 0 and rp < n and nList[lp] == nList[rp]:
        lp -= 1
        rp += 1
    dp[p + 1][0] = rp

    # case 2 -> 간격이 짝수
    lp = p
    rp = p + 1
    while lp >= 0 and rp < n and nList[lp] == nList[rp]:
        lp -= 1
        rp += 1
    dp[p + 1][1] = rp
    p += 1

for _ in range(int(input().strip())):
    s, e = map(int, input().split())
    mid = (s + e) // 2
    idx = 0
    if (s + e) % 2 != 0:
        idx = 1
    if dp[mid][idx] >= e:
        print(1)
    else:
        print(0)