[dp/백준] 10942번: 팰린드롬?

-문제: https://www.acmicpc.net/problem/10942

 

문자의 시작과 끝이 같은지 계속 비교해가면서 모두 같으면 팰린드롬이다. 

각자하면 시간이 오래 걸리므로 2차원 행렬을 만들어서 행은 시작점, 열은 끝점으로 지정한다음 

길이별로 팰린드롬 여부를 입력한다. 

여기서도 문자 길이가 1인지,2인지 3 이상인지에 따라 팰린드롬을 확인하는 여부가 다르기 때문에 

경우에 대해 잘 생각해야한다. 

 

자세한 풀이는 이 게시물을 확인하면 된다.

-정답풀이: 

import sys
input=sys.stdin.readline

n=int(input())
data=list(map(int,input().split()))
m=int(input())
dp=[[0 for _ in range(n)] for _ in range(n)]

for num_len in range(n): #문자열의 길이
    for start in range(n - num_len): #문자 시작 위치
        end= start + num_len 
        
        #문자 길이가 1임 -> 무조건 팰린드롬
        if start == end: 
            dp[start][end]=1
            
        #문자 길이가 2이상이고, 끝점이 같은 경우
        elif data[start]==data[end]:
            #문자 길이가 2인 경우
            if start+1 == end:
                dp[start][end] = 1
            #양 끝 숫자가 같고, 안에 숫자도 같은 경우
            elif dp[start+1][end-1] == 1:
                dp[start][end] = 1                
            
for _ in range(m):
    s,e=map(int,input().split())
    print(dp[s-1][e-1])

 

-시도해본 풀이

값이 입력될 때마다 완전 탐색으로 양끝을 비교한다.

이렇게 하면 시간초과한다 

n=int(input())
data=[0]+list(map(int,input().split()))
m=int(input())
flag=True

for _ in range(m):
    s,e=map(int,input().split())
    for i in range((e-s)//2 +1):
        if data[s+i] != data[e-i]:
            flag=False
    if not flag:
        print(0)
    else:
        print(1)