[백준 10942 펠린드롬? 문제] PYTHON

펠린드롬 문제 자체는 어렵지 않아 처음에는 아래 코드와 같이 간단하게 구현을 해봤다.

N = int(input())
Narray = list(map(int, input().split()))
M = int(input())

for _ in range(M):
    S, E = map(int, input().split())
    if Narray[S:E+1] == Narray[S:E+1][::-1]:
        print(1)
    else:
        print(0)

 

하지만 역시 골드 문제답게 호락호락하지 않아 시간초과로 False가 나왔다.

결국 여러 방법을 찾아보고 NxN 2차원 배열에 1,0으로 T/F로 저장을 해서 푸는 법을 알았다.

처음에 이런 방식을 생각하기는 했지만 이런 방식으로 풀면 N도 크고 M도 커서 시간 초과가 걸릴까 포기한 방법이다.

하지만 이 방법을 보고 N^2이라해도 400만 밖에 안돼 충분했다.

 

처음에 한 방법이 M의 크기가 커질수록 연산의 횟수가 늘어나지만 N은 최대 2000인 것에 비해 M은 최대 백만이어서  결국은 부적절한 방법이었다 생각한다. 

 

import sys
input = sys.stdin.readline
N = int(input())
Narray = list(map(int, input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(0, N+1):
    for start in range(1, N+1):
        end = start+i
        if end > N:
            break
        if i == 0:
            dp[start][end] = 1
            continue
        if i == 1 and Narray[start-1] == Narray[end-1]:
            dp[start][end] = 1
            continue
        if dp[start+1][end-1] and Narray[start-1] == Narray[end-1]:
            dp[start][end] = 1

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