[백준 DP] 10942 팰린드롬?

🥕 [ 백준 10942 ] 팰린드롬?

문제 링크

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

10942번: 팰린드롬?

 

🍒 문제 분석

 

0.5초의 시간 제한이 있는 문제. DP 사용 필요. (1000만번까지 연산 가능)

N 개의 문자열에 대해 팰린드롬인지 M번 질문. ( N은 2000 이하, M은 백만 이하 )

각 질문은 시작 인덱스 S, 끝 인덱스 E 로 이루어져 있음.

 

🍓 내 해결 과정

DP는 모든 케이스에 대해 바텀업으로 다 구해놓고, 그 이후 정답을 DP에서 뽑아내어 출력하는 것이 좋다.

 

팰린드롬 문자열의 길이 1부터 시작하여, for 문을 통해 (N-길이+1) 개 문자열에 대해 start 지점을 돌아준다.

( dp[i][j] ; i가 길이, j 가 start 지점 )

 

나눈 케이스

1. 문자열 길이가 1 일 때, 팰린드롬

2. 문자열 길이가 2 일 때, 배열의 시작, 끝이 같으면 팰린드롬

3. 문자열 길이가 3 이상일 때, 배열의 시작, 끝이 같다면 두 번째 시작, 끝에 대해 저장한 dp 값 호출

 

🥑 코드

import sys 
input = sys.stdin.readline
print = sys.stdout.write
ans = []

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

dp = [[0 for _ in range(N)] for _ in range(N)]

for length in range(1, N+1):
    for start in range(N-length+1):
        end = start + length-1

        # 길이가 1개 일 때
        if length == 1:
            dp[start][end] = 1
        # 길이가 2개 일 때
        elif length == 2:
            dp[start][end] = 1 if array[start]==array[end] else 0
        # 길이가 3 이상일 때, 배열 앞자리와 뒷자리가 같다면
        elif array[start] == array[end]:
            dp[start][end] = dp[start+1][end-1]
        # else : dp[start][end] = 0 (어차피 0이 저장되어있어서 이건 안써줘도 된다.)


for _ in range(M):
    S, E = map(int,input().rstrip().split())
    S, E = S-1, E-1
    ans.append(dp[S][E])


print('\n'.join(map(str,ans)))