백준 10942 [팰린드롬?] 파이썬

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

 

도저히 아이디어가 떠오르지 않았다..

 

<실패코드>

# 백준 10942 펠린드롬

import sys
from collections import deque
input=sys.stdin.readline

N=int(input())
nums=list(map(int,input().split()))
cases=[[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(N):
    left=deque()
    r_right=deque()
    odd_flag=True
    for j in range(i,N):
        if odd_flag:
            r_right.appendleft(nums[j])
            temp=r_right.pop()
            if left==r_right:
                cases[i+1][j+1]=1
            else:
                cases[i+1][j+1]=0
            # print('left',left)
            # print('r_right',r_right)
            left.append(temp)
            odd_flag=False
        else:
            r_right.appendleft(nums[j])
            if left==r_right:
                cases[i+1][j+1]=1
            else:
                cases[i+1][j+1]=0
            # print('left',left)
            # print('r_right',r_right)
            odd_flag=True
questions=[]
q_nums=int(input())
for _ in range(q_nums):
    questions.append(list(map(int,input().split())))

# print(cases)

for question in questions:
    start,end=map(int,question)
    print(cases[start][end])

시간복잡도가 O(N^3)이어서 시간초과가 발생하였다.

 

<성공 코드>

import sys
input = sys.stdin.readline

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

# 길이 3 이상
for length in range(3, N+1):
    for start in range(N-length+1):
        end = start + length - 1
        if nums[start] == nums[end] and dp[start+1][end-1]:
            dp[start][end] = 1

M = int(input())
for _ in range(M):
    s, e = map(int, input().split())
    print(dp[s-1][e-1])

GPT의 도움을 받아 해결하였다.

길이별로 팰린드롬을 계산하고, 이전에 계산한 팰린드롬을 이용값을 이용하여 양 끝 값이 같은지 확인하여 해결한다.

(DP를 이용)