[백준 BOJ / Python] 10942번 팰린드롬

문제

주어진 구간이 팰린드롬인지 빠르게 판단해 1 혹은 0을 출력하는 문제이다.

풀이

• DP를 사용해 각 구간이 팰린드롬인지 미리 계산하면, 명우의 질문에 대한 답을 빠르게 구할 수 있다.
  1. 길이가 1인 경우: 모든 숫자는 무조건 팰린드롬이다.
  2. 길이가 2인 경우: 두 숫자가 같은 경우만 팰린드롬이다.
  3. 길이가 3 이상인 경우: 양 끝의 두 숫자가 같고, 내부 숫자들이 팰린드롬일 때만 팰린드롬이 성립한다.
     팰린드롬의 길이가 3인 경우부터 차례로 DP를 사용해 팰린드롬 여부를 계산하면, 내부 구간을 비교할 수 있다.
• 이후 a에서 b까지의 구간에  대해 DP 테이블을 참조해 팰린드롬 여부를 빠르게 출력할 수 있다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp = [[0]*n for _ in range(n)]

# 길이가 1인 경우 팰린드롬 성립
for i in range(n):
    dp[i][i] = 1

# 길이가 2인 경우 두 개의 값이 같아야 팰린드롬 성립
for i in range(n-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = 1

# 길이가 3이상인 경우 양 끝이 같은 값이며, 내부가 팰린드롬이어야 성립
for k in range(2, n): # 팰린드롬 길이
    for i in range(n-k):
        if arr[i] == arr[i+k] and dp[i+1][i+k-1]:
            dp[i][i+k] = 1

m = int(input())
for _ in range(m):
    a,b = map(int,input().split())
    print(dp[a-1][b-1])

 

문제출처

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