[파이썬] 백준 10942 : 팰린드롬? (골드4)

[파이썬] 백준 10942 : 팰린드롬? (골드4)

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

---

풀이

방향성 생각

• 전형적인 DP
• 각 쿼리마다 체크하거나, $N^2$로 체크하면 시간초과한다.
  • 시간 제한이 0.5초이고 쿼리 개수가 많아서 DP 리스트에 접근하면 시간초과.
• DP를 통해서 순회를 줄인 후, 쿼리를 결과를 출력한다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
arr = list(map(int,input().split()))

dp = [[0]*(N) for _ in range(N)] #dp[시작idx][끝idx]

# 길이 1은 팰린드롬
for i in range(N):
    dp[i][i] = 1
# 길이 2는 서로 같으면 팰린드롬
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = 1
# 길이 3 이상은 시작점=끝점이고 시작점 다음 = 끝점 이전이면 팰린드롬
for leng in range(3,N+1):
    for s in range(N-leng+1):
        e = s+leng-1
        if arr[s] == arr[e] and dp[s+1][e-1]:
            dp[s][e] = 1

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

코멘트

• 시간 줄이려고 set 하나 만들어서 쿼리 입출력 시간 줄이려고 해봤는데 메모리 초과...