백준 10942번: 팰린드롬? (Python)

접근

생각보다 간단한 문제였다. dp[i][j]에 i부터 j까지 팰린드롬인지 저장하고, S, E에 대하여 팰린드롬인지 확인할 때에는 S + 1, E - 1이 팰린드롬인지 확인한 후, S, E에 해당하는 숫자가 같은지 확인하여 팰린드롬인지 아닌지를 판단하게 된다.

팰린드롬인 1, 2, 3, 2, 1 이 있다고 할 때, S, E = 1, 5 가 팰린드롬이기 위해서 S + 1, E - 1 = 2, 4 에 대해서도 수열이 팰린드롬이며, S, E에 해당하는 숫자가 1로 동일하다.

dp 수열을 만든 후 모든 칸을 채우고, 이후 입력받는 S, E값에 해당하는 값을 찾아서 표시해준다.

코드

import sys

n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
palindrome = [[0 for _ in range(n)] for __ in range(n)]

for i in range(n):
    palindrome[i][i] = 1
for i in range(n - 1):
    if numbers[i] == numbers[i + 1]:
        palindrome[i][i + 1] = 1
for x in range(2, n):
    for i in range(n - x):
        j = i + x
        if palindrome[i + 1][j - 1] == 1 and numbers[i] == numbers[j]:
            palindrome[i][j] = 1

for _ in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    print(palindrome[a - 1][b - 1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!