[Python - Dynamic Programming] 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을 출력한다.

📌 문제 풀이

👨‍🏫 접근

이걸 어떻게 다이나믹 프로그래밍으로 풀어야 하나 몇 시간을 고민했다.

 

일단 팰린드롬 수인지 구하는 방법부터 복기했다. 팰린드롬수는 우영우다. 그냥 읽어도 우영우 거꾸로 읽어도 우영우. 그렇게 좌우 대칭인 수를 팰린드롬 수라고 한다.

 

팰린드롬인지 확인하기 위해서 투 포인터 알고리즘을 생각했다. pl과 pr이 가리키는 수가 동일하며, 계속 이동해서 서로가 교차하게 된다면 그것은 팰린드롬 수라는 반증이다.

 

처음에는 모든 자리에 팰린드롬 연산을 했었는데 시간이 너무 오래 걸렸다. 그런데 다시 생각해보니, 팰린드롬으로 좌우를 좁히다보면 내가 이전에 팰린드롬인지 검사하던 수였으면 그 수의 팰린드롬 여부만 검사해도 된다.

 

예를 들어 1, 2, 3, 3, 2, 1이라는 수열을 검사할 때, 이미 2, 3, 3, 2 라는 수열이 팰린드롬인 것을 알고 있다면, 양 끝에 있는 1과 1만 비교하고 나머지는 비교하지 않아도 되는 것이다. 이런 식으로 다이나믹 프로그래밍을 진행한다.

 

다이나믹 프로그래밍은 대략적인 맥락이 있다.

for 반복:
    d[현재] = min/max/d[과거] + 값

혹은 재귀를 사용해서,

def recursion(k):
	if k는 1:
    	return 참, 거짓, n 등
    if d[k] == 방문함:
    	return d[k]
    
    d[k]는 recursion(k - 연산):
    return d[k]

여기서 for 반복을 두 번 사용한다거나 하는 등으로 변형이 된다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def find(pl, pr):
    if arr[pl] != arr[pr]:
        return 0
    if d[pl][pr] or pl > pr:
        return 1

    d[pl][pr] = find(pl + 1, pr - 1)
    return d[pl][pr]


n = int(input())
arr = [0] + list(map(int, input().split()))
m = int(input())

d = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    d[i][i] = 1
    for j in range(i + 1, n + 1):
        d[i][j] = find(i, j)

for _ in range(m):
    s, e = map(int, input().split())
    print(d[s][e])

📄 준비

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def find(pl, pr):
    if arr[pl] != arr[pr]:
        return 0
    if d[pl][pr] or pl > pr:
        return 1

    d[pl][pr] = find(pl + 1, pr - 1)
    return d[pl][pr]


n = int(input())
arr = [0] + list(map(int, input().split()))
m = int(input())

d = [[0] * (n + 1) for _ in range(n + 1)]

재귀를 사용할 땐 항상 sys 모듈의 setrecursionlimit 메서드로 재귀 최대 깊이를 늘려준다.

 

팰린드롬인지 확인하는 함수를 생성했다. 좌우 값이 다르면 어떻게 하든 팰린드롬이 아니기 때문에 0을 리턴한다. 만약 둘이 교차되었거나, 이미 이전에 팰린드롬인지 검사했던 수라면 1을 리턴한다. 이 값을 매번 테이블에도 저장해준다.

 

문제에서 입력의 인덱스가 1부터 시작하기에 n + 1로 범위를 더 늘려서 받았다. arr도 그것을 고려했다.

📄 풀이

for i in range(1, n + 1):
    d[i][i] = 1
    for j in range(i + 1, n + 1):
        d[i][j] = find(i, j)

for _ in range(m):
    s, e = map(int, input().split())
    print(d[s][e])

자기 자신은 무조건 팰린드롬수이기 때문에 자기 자신은 1로 저장하고 시작한다.

📌 총평

아 너무 뿌듯하다 :^DDD