[알고리즘] BOJ 10942 팰린드롬? #Python

[BOJ] 10942 팰린드롬? 바로가기

📍 문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

---

📍 입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

---

📍 출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

---

📍 풀이

🧷 풀이 과정

📒 참고한 블로그

동적 프로그래밍(Dynamic Programming)을 적용하여 문제를 해결하였다.

칠판에 적은 수에 존재하는 모든 팰린드롬을 미리 구하는 방식을 사용하였다.
길이가 1인 숫자부터 길이가 N인 숫자들을 차례로 팰린드롬인지 아닌지를 누적으로 확인하는 방법을 이용하였다.

🧷 예시

• N = 5
• number = [1, 2, 2, 2, 1]
• 1, 2 .. N-1, N 길이에 해당하는 팰린드롬 찾기
  • 길이가 1인 팰린드롬 → 1, 2, 2, 2, 1
  • 길이가 2인 팰린드롬 → (2, 2), (2, 2)
  • 길이가 3인 팰린드롬 → (2, 2, 2)
  • 길이가 4인 팰린드롬 → None
  • 길이가 5인 팰린드롬 → (1, 2, 2, 2, 1)

길이가 1 인 팰린드롬은 모두 팰린드롬으로 처리한다.
길이가 2 인 팰린드롬은 직접 비교(number[i] == number[i+1])를 통해 팰린드롬으로 처리한다.
길이가 3 이상이 팰린드롬은 가장 자리의 숫자가 같으면서(number[s] == number[e]), 가장 자리의 숫자를 제외한 내부 숫자가 팰린드롬(dp[s+1][e-1] == True)이면 팰린드롬으로 처리한다.

위 예시에서 길이가 5인 팰린드롬(1, 2, 2, 2, 1)을 예로 설명하면 다음과 같다.

1. 가장 자리의 숫자를 비교한다.
   • 첫 번째 숫자(1)와 마지막 숫자(1)이 같다.
2. 가장 자리의 숫자를 제외한 내부 숫자가 팰린드롬인지 확인한다.
   • 가장 자리의 숫자를 제외한 내부 숫자(2, 2, 2)는 길이가 3인 팰린드롬(2, 2, 2)에서 팰린드롬으로 처리하였으므로 내부 숫자는 팰린드롬이다.

✍ 전체 코드

# BOJ 10924 팰린드롬?
# https://www.acmicpc.net/problem/10942

from sys import stdin

def solution(N, number, M, Q):

    dp = [[False] * (N+1) for _ in range(N+1)]
    for i in range(0, N+1):
        for j in range(1, N+1-i):
            s, e = j, j+i
            if s == e:
                dp[s][e] = True
            elif s+1 == e and number[s] == number[e]:
                dp[s][e] = True
            elif dp[s+1][e-1] and number[s] == number[e]:
                dp[s][e] = True
    
    for d in dp: print(d)
    
    for S, E in Q:
        print(1 if dp[S][E] else 0)

N = int(stdin.readline())
number = [0] + list(map(int,stdin.readline().split()))
M = int(stdin.readline())
Q = list(list(map(int,stdin.readline().split())) for _ in range(M))

solution(N, number, M, Q)