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

10942번: 팰린드롬?

팰린드롬은 문자열이 주어졌을때 왼쪽으로 부터 읽었을때와 오른쪽에서부터 읽었을때가 같을때 팰린드롬이라고 합니다.

해당 문제는 다이나믹 프로그래밍 문제로 다음과 같은 아이디어에서 문제를 해결 할 수 있습니다.

dp[n][m]이 있을때 문자열 n부터 m까지의 팰린드롬인지 아닌지를 구분하는 역할을 한다.

dp[n][m]은 현재 문자열 arr[n] == arr[m]이 같다면 dp[n+1][m-1]이 팰린드롬인지 아닌지만 판별하면 dp[n][m]이 팰린드롬인지 아닌지 알수 있습니다.

예시

dp[0][0] ... dp[n][n] 은 자기자신임으로 팰린드롬 입니다.

dp[0][1] … dp[n-1][n]은 arr[n-1] 과 arr[n]이 같다면 팰린드롬 입니다.

dp[0][2]는 arr[0], arr[2]가 같고, dp[1][1]이 팰린드롬이라면 팰린드롬입니다.

import sys
input = sys.stdin.readline

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

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

for i in range(N): # 길이가 1인 펠린드롬
    dp[i][i] = 1

for i in range(N - 1): # 길이가 2인 펠린드롬
    if arr[i] == arr[i + 1]:
        dp[i][i + 1] = 1
    else:
        dp[i][i + 1] = 0

for i in range(2, N): # 길이가 3이상인 펠린드롬 ( N펠린드롬을 구할때 N-1 펠린드롬을 참고하여 구한다.)
    for j in range(N - i):
        if arr[j] == arr[j+i]:
            dp[j][j+i] = dp[j+1][j+i-1]
        else:
            dp[j][j+i] = 0

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