문제링크

10942 - 펠린드롬?

문제설명

N개의 자연수에 대해서 M번의 질문을 받는다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지 물어본다. 펠린드롬이면 1을, 아니면 0을 반환한다.

문제풀이

DP로 풀이하는 문제이다.
nums[S:E+1]에 대해서 해당 문자가 펠린드롬이기 위해서는
-> nums[S] == nums[E]이고, nums[S-1:E]가 펠린드롬이어야 한다.
여기서 nums[S-1:E]의 부분을 DP로 처리한다.

크게 세가지 경우로 나누어서 풀이했다.

1. 문자열의 길이가 1인 경우
   이때는 무조건 팰린드롬이다.
2. 문자열의 길이가 2인 경우 (E=S+1)
   nums[S]==nums[S+1]이면 팰린드롬이다.
3. 문자열의 길이가 3인 경우
   nums[S] == nums[E]이고, nums[S-1:E]

import sys

input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
M = int(input())
questions = []
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):
    if nums[i] == nums[i+1]:
        dp[i][i+1] = 1

for l in range(2, N):
    # 길이가 3 이상
    for i in range(N-l):
        # 처음 문자 == 마지막 문자 && dp[처음+1][마지막-1]
        if nums[i] == nums[i+l] and dp[i+1][i+l-1] == 1:
            dp[i][i+l] = 1


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

dp는 참 한번에 떠올리기 어려움,,