[Algorithm] 백준 10942번: 팰린드롬? | 동적 계획법 응용

문제 출처: https://www.acmicpc.net/problem/10942

---

1. 결과

메모리 60000KB, 시간 1816ms

2. 풀이

동적 계획법을 다루는 문제에서 팰린드롬(Palindrome)은 대표적인 예제 중 하나이다. ABA, ABCBA와 같이 앞에서 한 글자씩 읽어도, 뒤에서 한 글자씩 읽어도 같은 문자열이 되는 경우를 팰린드롬이라고 한다.

주어진 문자열에서 가능한, 가장 긴, 연속된 팰린드롬 문자열의 길이를 구하는 문제가 팰린드롬 관련 문제 중 가장 기초가 되는 문제이고, 그 외에 가장 긴 팰린드롬 자체를 구하는 문제나 이 문제처럼 팰린드롬의 여부를 묻는 문제도 있다. 여기서 말한 다른 팰린드롬 문제는 블로그에 알고리즘 풀이를 기록하기 이전에 풀어봤기 때문에 아직 없지만, 추후에 특정 테마에 관련된 문제들을 한 번에 모아서 정리해보거나, 이전의 풀이도 하나씩 다시 풀어보면서 블로그에 작성할 예정이다.

어쨌든 이 문제는 동적 계획법을 이용하는 팰린드롬 문제라는 부분에서 다른 문제와 유사하다. 단, 조건을 섬세하게 다시 잘 구분해야 한다. 내가 풀이를 고민하며 떠올린 조건은 아래와 같다. 우선 주어진 문자열을 각각 행(i)과 열(j)에 나열하고 모든 시작점(S)과 끝점(E)의 경우를 고려하고 저장해야 한다. 만약 특정 S와 E마다 새로 값을 계산하려고 하면 시간 초과가 발생하기 때문이다. 이는 한 번 계산한 값은 저장하는 동적 계획법의 장점을 이용하라는 의미이다. 그리고 실제로 이를 계산하는 조건은 아래 순으로 작성했다. 문자열 abac를 예시로 들었고, 모든 시작점(행)에 따라 모든 끝점(열)을 계산하므로 i == j를 기준으로 오른쪽 위 삼각형만 채우면 된다.

오른쪽이 열(j) 아래가 행(i)	a	b	a	c
a
b	x
a	x	x
c	x	x	x

1. i == j일 때, 즉 자기자신 한 글자인 경우이므로, 팰린드롬이다. -> 1

오른쪽이 열(j) 아래가 행(i)	a	b	a	c
a	1
b	x	1
a	x	x	1
c	x	x	x	1

2. 문자열[i] == 문자열[j]일 때

1) 문자열[i+1] 부터 문자열[j-1]까지가 팰린드롬이라면(표[i+1][j-1] == 1), 표[i][j]는 팰린드롬이다. -> 1

2) i부터 j까지가 같은 두 문자열(만약 주어진 문자열이 abba인 경우에 발생 가능한 상황)인 경우(문자열[i] == 문자열[j]이고, i + 1 = j)에도 표[i][j]는 팰린드롬

오른쪽이 열(j) 아래가 행(i)	a	b	a	c
a	1	0	1	0
b	x	1	0	0
a	x	x	1	0
c	x	x	x	1

이와 같이 먼저 주어진 문자열에 대한 팰린드롬 여부를 저장한 표를 구하고, 입력으로 주어지는 각 S, E를 인덱싱으로 이용하면 된다.

import sys

# 팰린드롬 여부를 저장하는 2차원 리스트. i == j인 경우는 모두 1
# data[i] == data[j]일 때, data[i+1] 부터 data[j-1]까지가 팰린드롬이라면(pal[i+1][j-1] == 1), i, j일 때도 팰린드롬
# data[i] == data[j]일 때, i부터 j까지가 같은 두 문자열( ex) aa)이라면(i + 1 == j), i, j일 때도 팰린드롬
def isPal(data, n):
    pal = [[0] * n for _ in range(n)]

    for i in range(n-1, -1, -1):
        for j in range(i, n):
            if i == j: pal[i][j] = 1
            elif data[i] == data[j]:
                if pal[i+1][j-1]: pal[i][j] = 1
                elif i + 1 == j: pal[i][j] = 1
    
    return pal

def main():
    N = int(sys.stdin.readline())
    nums = sys.stdin.readline().split()
    M = int(sys.stdin.readline())
    pal_arr = isPal(nums, N)
    
    for _ in range(M):
        start, end = map(int, sys.stdin.readline().split())
        print(pal_arr[start-1][end-1])
    
    return

if __name__ == "__main__":
    main()