[PS] BOJ 10942 / 팰린드롬?

Minjun Kim

23 Jul 2025 • 3 min read

문제 링크: https://www.acmicpc.net/problem/10942

Thumbnail: Photo by Josh Nezon (Unsplash)

문자열이 회문인지 아닌지 판단하는 문제입니다. 그러나, 전체 문자열의 임의의 부분에 대해서 회문인지 아닌지를 여러 번 판단해줘야 합니다.

풀이

이 문제를 푸시는 분들은 회문이 무엇인지 모두 아실거라고 생각합니다! 간단히 이야기하면, 문자열을 반으로 잘랐을 때 대칭인 경우 회문입니다.

단순히 회문인지 판단하려면, 문자열의 앞에서 절반과 뒤에서 절반을 비교해주면 됩니다. 그러나, 이번 문제에서는 회문 판단을 여러 번 해야 하지만 시간 제한은 짧은 편입니다. (0.5초, PyPy3 1.5초)

매 구간마다 회문 여부를 계속 판단한다면, 시간 초과를 맞이하게 됩니다. 따라서, 판단 결과를 저장하고 재활용 해야 합니다. 즉, DP입니다!

DP 배열 구성하기

DP 배열은 다음과 같이 구현했습니다.

DP[S][E] = 전체 문자열의 S부터 E까지의 부분이 회문인지 아닌지의 여부.

회문이라면 1, 아니라면 0을 저장합니다.

먼저, DP[1][1]부터 DP[N][N]까지, 길이 1짜리 문자열은 항상 회문이므로 DP값을 1로 초기화해주고 나머지 칸은 -1 (계산되지 않음) 으로 초기화합니다.

N = int(input())
arr = list(map(int, input().split()))
DP = [[-1] * 2000 for _ in range(2000)]

for i in range(N):
    DP[i][i] = 1

DP 배열 초기화

이후, 매번 구간을 입력받을 때마다 DP 배열을 갱신합니다.

def check_palindrome(s, e):
    if s >= e:
        return 1
    if DP[s][e] == -1:
        DP[s][e] = int(check_palindrome(s + 1, e - 1) == 1 and arr[s] == arr[e])

    return DP[s][e]

for _ in range(int(input())):
    S, E = map(lambda x: int(x) - 1, input().split())
    print(check_palindrome(S, E))

DP 갱신

DP 점화식은 다음과 같습니다.
DP[S][E] = DP[S+1][E-1] == 1 && arr[s] == arr[e]

check_palindrome은 재귀를 통해 DP 배열을 갱신하며, 이미 계산된 구간의 경우 별도의 계산 없이 저장된 값을 바로 반환합니다. (memoization)

전체 코드

input = open(0).readline
N = int(input())
arr = list(map(int, input().split()))
DP = [[-1] * 2000 for _ in range(2000)]

for i in range(N):
    DP[i][i] = 1

def check_palindrome(s, e):
    if s >= e:
        return 1
    if DP[s][e] == -1:
        DP[s][e] = int(check_palindrome(s + 1, e - 1) == 1 and arr[s] == arr[e])

    return DP[s][e]

for _ in range(int(input())):
    S, E = map(lambda x: int(x) - 1, input().split())
    print(check_palindrome(S, E))

solution.py