BOJ 10942(팰린드롬?)풀이

solved.ac 티어 : 골드 2

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

이문제는 단순하게 입력으로 들어오는 구간마다 하나씩 비교하면서 처리하는 방식은 시간 초과가 난다.

그럼 어떻게 할 수 있을까? 예를 들어 1 2 1 1 2 1 이면 배열이 있고 1 6이라는 입력이 들어왔다.

1 2 1 1 2 1은 팰린드롬이기 때문에 1을 출력해야 한다.

이때 양끝을 제외한 나머지가 팰린드롬이고 양쪽이 같을 경우 팰린드롬이 된다. 

이걸 계속 적용한다면 범위의 값이 팰린드롬인지 아닌지를 알 수 있고 이건 dp로 구할 수 있다.

처음에는 end-start=0 그다음에는 1,2,3.... n-1 순으로 비교를 하면서 dp 배열에 그 구간이 팰린드롬인지 아닌지를 저장하면 된다.

팰린드롬 판별은 범위의 양 끝 값이 같고 dp[start+1][end-1]이 1일 경우 팰린드롬이다.((end-start+1)이 1과 2일 경우만 예외 처리해주면 된다.)

 

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
dp=[[0 for i in range(2010)]for g in range(2010)]
a=int(input())
l=list(map(int,input().split()))
for i in range(a):
    start=0
    for end in range(i,a):
        if start==end:
            dp[start][end]=1
        elif end-start==1:
            if l[start]==l[end]:dp[start][end]=1
        elif l[start]==l[end] and dp[start+1][end-1]==1:
            dp[start][end]=1
        start+=1
b=int(input())
for i in range(b):
    c,d=map(int,input().split())
    print(dp[c-1][d-1])

혼자 푼 dp라 기분이 좋다~ ㅎㅎ