[Python] 10942 - 팰린드롬?

[Gold IV] 팰린드롬? - 10942 

[문제 링크](https://www.acmicpc.net/problem/10942)

🗝️알고리즘 분류

• 다이나믹 프로그래밍

---

💻문제 정의

길이가 N인 수열에 대해, 질문이 M개 들어온다. 질문은 두 개의 정수 a, b이고, 수열 a번째 부터 b번째 사이의 수가 팰린드롬 수인지를 판별하는 문제이다.

 

💡접근 및 설계

기존의 팰린드롬 수를 구하는 알고리즘을 활용하였으나, 시간초과가 떳다.

이후 문제의 유형을 알아보니 DP를 활용하는 문제였다.

 

주어진 수열에 대해, 자른 수열의 길이가 1인 경우는 무조건 팰린드롬.

길이가 2인 경우, 두 수가 같을 경우 팰린드롬.

길이가 3 이상인 경우 처음과 끝이 같은 수이고, 처음과 끝을 제외한 수가 팰린드롬 수 일 경우 팰린드롬

 

다음의 세 가지 case를 두어 문제를 해결하였다.

 

✏️알고리즘 풀이

for i in range(N): # (1, 1), (3, 3) 등 한자리 수는 1
    dp[i][i] = 1

for j in range(N-1): # 두 자리의 경우, 두 문자가 같을 경우 1, 다를 경우 0
    if (lst[j] == lst[j+1]):
        dp[j][j+1] = 1
    else:
        dp[j][j+1] = 0

for cnt in range(N-2): # 세 자리에 경우, 양 끝이 같고 안에 문자가 1이면 1, 아니면 0
    for i in range(N-2-cnt):
        j = i + 2 + cnt
        if (lst[i] == lst[j]) and (dp[i+1][j-1] == 1):
            dp[i][j] = 1

먼저, 1부터 1, 3부터 3 같은 경우는 길이가 1인 수열로 판단된다. 따라서 이는 무조건 팰린드롬이다.

길이가 2인 경우, 두 수가 같을 경우 이는 팰린드롬이다.

길이가 3인 경우는 처음과 끝의 수가 같고, 중간의 수열이 팰린드롬수일 경우 이는 팰린드롬수이다.

dp의 결과를 표로 본다면 다음과 같다.

 

 

🗒️제출 코드

# 10942 팰린드롬?

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
dp = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N): # (1, 1), (3, 3) 등 한자리 수는 1
    dp[i][i] = 1

for j in range(N-1): # 두 자리의 경우, 두 문자가 같을 경우 1, 다를 경우 0
    if (lst[j] == lst[j+1]):
        dp[j][j+1] = 1
    else:
        dp[j][j+1] = 0

for cnt in range(N-2): # 세 자리에 경우, 양 끝이 같고 안에 문자가 1이면 1, 아니면 0
    for i in range(N-2-cnt):
        j = i + 2 + cnt
        if (lst[i] == lst[j]) and (dp[i+1][j-1] == 1):
            dp[i][j] = 1

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

---