백준(BOJ) 10942 팰린드롬?(Python)

문제 내용.

 

DP 문제.

먼저 2차원 DP를 생성한다.

palindrome[i][j]는 i부터 j까지가 팰린드롬이면 1, 그렇지 않으면 0을 저장한다.

j-i가 0이면 1, 1이면 i번째 문자와 j번째 문자가 같은 경우 1, 그렇지 않으면 0을 저장한다.

만약 j-i가 2 이상인 경우에는 k를 변화시키며 양 끝 각각 k개가 서로 같고, 그 중앙에 있는 문자열이 팰린드롬인지를 확인한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n=int(input())
X=list(map(int,input().split()))
palindrome=[[0]*n for _ in range(n)]
for i in range(n):
    palindrome[i][i]=1
for i in range(n-1):
    if X[i]==X[i+1]:
        palindrome[i][i+1]=1
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        if X[j]==X[k] and palindrome[j+1][k-1]:
            palindrome[j][k]=1
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(palindrome[a-1][b-1])

나도 아는 웰 노운.