[Python] G4_10942_팰린드롬 ❓

https://www.acmicpc.net/problem/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을 출력한다.

예제

코드

import sys
input = sys.stdin.readline

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

for i in range(N): # i는 글자 수를 의미
    for start in range(N-i):
        end = start+i # 확인할 시작점과 끝점
        # 한 글자인 경우
        if start == end:
            dp[start][end] = 1
        # 두 글자 이상이고, 양 끝이 같은 경우
        elif lst[start] == lst[end]:
            # 두 글자인 경우
            if start+1 == end:
                dp[start][end] = 1
            # 가운데가 팰린드롬인 경우
            elif dp[start+1][end-1]:
                dp[start][end] = 1             
                
for _ in range(M):
    a,b = map(int,input().split())
    print(dp[a-1][b-1])

우선은 팰린드롬이 되는 조건부터 생각해보아야 한다.

팰린드롬이 되는 경우는 다음과 같다.

1. 한글자인 경우

2. 두글자이며, 두 개가 같은 경우

3. 세글자 이상이며, 양 끝이 같고 가운데가 팰린드롬인 경우

풀어서 설명해보도록 하겠다.

• 한글자인 경우 에는 당연히 팰린드롬이 된다.

• 두글자인 경우 에는 1 1과 같이 두 개가 같다면 팰린드롬이 된다.

• 세글자 이상인 경우에는 1 2 1과 같이 양 끝이 같고 가운데가 팰린드롬인 경우에는 팰린드롬이 된다.

글자 수를 1개씩 추가해가며, 팰린드롬인지의 여부를 담은 dp를 서서히 채워나간다.

다섯글자인 경우를 한 번 봐보자.

예제에서 2 1 3 1 2는 우선 양 끝이 같다. 그리고 가운데 1 3 1이 팰린드롬이다. 그렇기 때문에 2 1 3 1 2도 팰린드롬이 된다.

이는 세글자인 경우에서 이미 1 3 1을 dp에 저장해두었기 때문에, 양 끝이 같음만 파악하여 바로 알아낼 수 있다.

이러한 과정을 반복해주면, 이전의 결과를 통해서 빠르게 팰린드롬을 찾아줄 수 있다.

테스트케이스 마다 답을 출력해준다.

리스트의 인덱스들을 입력받은 후에, 2차원 배열 dp에서 이를 꺼내 팰린드롬인지 아닌지를 출력해주면 된다.

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

느낀 점 & 배운 점

1. 팰린드롬을 이런 식으로 빠르게 찾을 수 있겠구나라는 걸 알게 되었다. 후에 다른 문제에도 적용할 수 있을 것 같다.

2. dp는 아직도 약하다.. 적어도 태그 레벨 G3이 될 때까지는 열심히 풀어보자.