[백준] 10942 - 펠린드롬? (G3)

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다.

(그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.)

 

펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다.

어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다.

따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면

dp[s][e] = dp[s+1][e-1] + 2

이다.

단, 위 점화식의 조건은 dp[s+1][e-1] 의 펠린드롬 길이가 1 이상이어야 하고,

str[s] == str[e] 이어야 한다.

만약 두 조건중 하나라도 충족이 되지 않으면 dp[s][e] = 0 이다.

 

구현하는 방법에는 여러가지 방법이 있겠지만, 나는 탑다운 방식으로 구현했다.

그냥 쿼리가 주어질때마다 해당 쿼리에 대해 dp[s][e]의 값을 찾고,

만약 이 값이 아직 결정되지 않았다면 탑다운 방식으로 펠린드롬 길이를 구하고,

구하는 과정에서 확인한 모든 구간에 대해 dp 테이블을 채우면 된다.

 

난이도 의견에도 남겼지만, 개인적으로 구간 DP에 대한 아이디어를 떠올릴 수 있었다면,

이 문제는 어렵지 않게 풀 수 있었다고 생각한다.

DP 알고리즘을 설명할 때 항상 나오는 피보나치 수 구하는 알고리즘과 비슷하다.

 

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

def isPalindrome(s, e):
    if s == e:
        dp[s][e] = 1
        return True

    if e - s == 1 and nums[s] == nums[e]:
        dp[s][e] = 2
        return True

    if dp[s][e] == -1:
        if nums[s] == nums[e] and isPalindrome(s+1, e-1):
            dp[s][e] = dp[s+1][e-1] + 2
            return True
        else:
            dp[s][e] = 0
            return False

    return dp[s][e] > 0

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

dp = [[-1 for _ in range(n+1)] for _ in range(n+1)]

m = int(input())
for _ in range(m):
    s, e = map(int, input().split())
    if isPalindrome(s, e):
        print(1)
    else:
        print(0)

 

코드를 읽어보니 함수 이름과 리턴값을 구할 때 이용하는 DP 값의 의미가 다른게 걸려서

아래와 같이 더 직관적으로 수정했습니다.

 

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

def isPalindrome(s, e):
    if nums[s] != nums[e]:
        dp[s][e] = False
    elif e - s < 2:
        dp[s][e] = True
    elif dp[s][e] == None:
        dp[s][e] = isPalindrome(s+1, e-1)

    return dp[s][e]

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

dp = [[None for _ in range(n+1)] for _ in range(n+1)]

m = int(input())
for _ in range(m):
    s, e = map(int, input().split())
    print(1 if isPalindrome(s, e) else 0)