[백준][Python][10942][DP] 팰린드롬?

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

10942번: 팰린드롬?

DP 문제다.

 

문제의 핵심은 길이가 1,2, 그 이상일때의 경우를 각각 나누는 것이다. (1은 참 0은 거짓이라 하자)

dp 배열은 dp[처음][끝] -> 처음 - 끝까지 했을 때 팰린드롬 인가? 이다.

1. 길이가 1 = 무조건 1
2. 길이가 2 = 두 문자가 같으면 1
3. 길이가 3 이상 -> 처음 문자 == 끝 문자 && dp[처음+1][마지막-1] 이 1

 

import sys

n = int(input())

d = [int(i) for i in sys.stdin.readline().split()]
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 d[i] == d[i+1]:
        dp[i][i+1] = 1

for l in range(2,n): # 길이가 3 이상
    for i in range(n-l):
        if d[i] == d[i+l] and dp[i+1][i+l-1] == 1:
            dp[i][i+l] = 1

qn = int(input())

for _ in range(qn):
    i,j = [int(a) for a in sys.stdin.readline().split()]
    print(dp[i-1][j-1])