백준: 10942 팰린드롬?

문제

10942번: 팰린드롬?

 

문제 풀이

 수열이 주어지고, 수열 중 일부를 선택할 때 선택한 부분이 회문(Palindrome)인지 여부를 반환하는 문제이다. 이 문제를 풀기 전까지는 시간이 충분히 주어지는 회문 문제들을 풀어서, 단순히 list를 조작하는 방식으로 회문을 찾았다. 하지만 이 문제는 그런 식으로 풀면 시간 초과가 발생한다.

 

 다른 DP 문제들과 마찬가지로, 메모이제이션을 통해 길이가 1부터 N까지의 늘려가며 회문인지 여부를 리스트에 기록해두는 방식을 사용한다.

 

 다음과 같이 지정된 범위에 따라 회문의 여부를 결정할 수 있다.

 

• 길이가 1인 경우
  • 무조건 회문이다.
• 길이가 2인 경우
  • 시작과 끝이 동일한 문자이면 회문이다.
• 길이가 3이상인 경우
  • 시작과 끝이 같고 dp[시작  + 1][끝 - 1]이 회문이면 회문이다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    seq = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    sections = [list(map(int, stdin.readline().split())) for _ in range(m)]
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = 1

    for i in range(1, n):
        # 길이가 1이면 회문.
        dp[i][i] = 1

        # 길이 2의 회문 확인.
        if seq[i - 1] == seq[i]:
            dp[i - 1][i] = 1

    for i in range(2, n):
        for j in range(n - i):
            # 길이 3이상의 회문 확인.
            if seq[j] == seq[i + j] and dp[j + 1][i + j - 1]:
                dp[j][i + j] = 1

    for section in sections:
        s, e = section
        print(dp[s - 1][e - 1])

 위의 코드와 같이 길이가 1, 2인 회문을 먼저 체크한 후, 2중 반복문을 통해 길이 3 이상의 회문을 체크한다.