[백준] 10942. 팰린드롬? - python

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

난이도: 골드4

알고리즘: DP

풀이과정

가장 먼저 확인했던 부분은 입력의 크기로, 팰린드롬인지 검사하는 횟수인 M의 크기가 1,000,000이다. 따라서 주어진 수열이 팰린드롬인지 O(1) 또는 O(log N)의 시간에 확인해야 한다.

수열의 길이인 N의 최대 크기는 2,000으로, DP를 활용하여 dp[start][end]를 통해 start부터 end까지의 숫자가 팰린드롬인지를 갱신하면 된다.

참고로 입력이 상당히 크므로, sys.stdin.readline을 사용하지 않으면 시간초과가 나므로 꼭 적어줘야 한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
nums = [-1]  # 0번째 인덱스
nums.extend(list(map(int, input().split())))
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][i] = 1
for i in range(1, n):
    if nums[i] == nums[i + 1]:
        dp[i][i + 1] = 1
for k in range(2, n):
    for start in range(1, n - k + 1):
        end = start + k
        if nums[start] == nums[end] and dp[start + 1][end - 1]:
            dp[start][end] = 1

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