문제 링크

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

문제 설명

• 2000개 숫자가 주어짐
• 100만개 start, end 인덱스가 주어짐
• start ~ end 가 팰린드롬이면 1, 아니면 0 출력

풀이

• dp 배열을 놓는다

• dp[s][e] : s~e가 팰린드롬이면 1, 아니면 0

• 양 끝이 같고 사이가 팰린드롬이면 1

• bottom-up으로 순회

  • 즉, 사이가 bottom

• 숫자가 2000개라 O(N^2) 가능
  

파이썬 코드

import sys


def solution():

    # 입력 받기
    read = sys.stdin.readline
    write = sys.stdout.write
    n = int(read())
    numbers = list(map(int, read().split()))
    m = int(read())
    questions = [list(map(int, read().split())) for _ in range(m)]

    # dp[i][j] s=i, e=j 일때 팰린드롬이면 1, 아니면 0
    dp = [[0]*n for _ in range(n)]

    # 길이가 1일 때
    for i in range(n):
        dp[i][i] = 1

    # 길이가 2일 때
    for i in range(n-1):
        if numbers[i] == numbers[i+1]:
            dp[i][i+1] = 1

    # 나머지
    num = 2
    while True:
        s, e = 0, num
        while True:
            # 양끝이 같고 사이가 팰린드롬이면
            if numbers[s] == numbers[e] and dp[s+1][e-1] == 1:
                dp[s][e] = 1
            s += 1
            e += 1
            if e == n:
                break
        num += 1
        if num == n:
            break

    # 프린트
    # for line in dp: print(line)

    for s, e in questions:
        write(f'{dp[s-1][e-1]}\n')


solution()