악곱 == 악성곱슬

DP

---

이 문제는 문자열이 하나 주어지고 인덱스가 최대 100만번 주어지는데, 이에 대해 팰린드롬인지 검사하는 문제이다.

문자열이 최대 2000, 쿼리가 최대 100만, 저것만 곱해봐도 20억이다. 따라서 미리 문자열에 대해 모든 팰린드롬을 2차원 배열로 구현한 후 결과를 쿼리마다 반환해야 하는 것을 알 수 있다.

일단 팰린드롬이란 중심을 기준으로 좌우가 대칭이 되는 문자열을 말한다. 크기가 1일 때는 팰린드롬이 맞다고 한다.

따라서 독특한 성질을 갖는다. 인덱스 1~100이 팰린드롬임을 알아보기 위해서는 2~99가 팰린드롬인지 알아야 하고 또 이를 알기 위해서는 3~98이 팰린드롬인지 확인해야 한다. 따라서 이를 미리 테이블로 저장해놓는다면 효율적으로 처리할 수 있다. 따라서 수많은 중복문제를 제거하기 위해 DP를 사용해야 함을 알 수 있다.

점화식은 다음과 같다.

즉, s, e의 차이가 1이거나 0이라면 그냥 문자열끼리만 비교해서 dp table을 초기화 한다.

그리고 2이상 차이나는 부분부터 s+1, e-1이 팰린드롬인지 검사하고 문자열 s, e가 같은지 비교하면 된다.

이를 코드로 구현하면 다음과 같다.

구현

---

2차원 배열의 행은 시작 문자열 인덱스 위치를 뜻하고, 열은 끝 문자열 인덱스 위치를 뜻한다. 따라서 행, 열은 s, e에서의 팰린드롬인지 여부를 저장한다.

그리고 해당 점화식은 s+1, e-1 에 대한 값이 있다는 것을 보장하기 위해, 2차원 배열을 오른쪽 대각선 아래방향으로 훑으며 지나가야 한다는 점이다.

• 즉, 부분 문자열이 짧은 순으로 업데이트 해야 한다는 것.
• ex): 가로 → 세로 순으로 훑으며 dp table을 업데이트 한다면 값이 올바르게 저장되지 않는다. why? 위 사진의 예시대로, 1→7은 palindrome이 맞는데, 2→6 보다 먼저 update되어 2→6이 palindrome인지 아닌지도 모른 상태에서 “1→7이 palindrome이 아니다” 라는 틀린 값을 저장하고 있을 수 있음

import sys

def dp(n):
    # 초기화
    for i in range(1, n+1):
        table[i][i] = 1

    for i in range(1, n):
        if numbers[i] == numbers[i+1]:
            table[i][i+1] = 1

    for offset in range(2, n):
        for i in range(1, n - offset + 1):
            x, y = i, i+offset
            if numbers[x] == numbers[y] and table[x+1][y-1] == 1:
                table[x][y] = 1

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
    M = int(sys.stdin.readline().rstrip())
    table = [[0] * (N+1) for _ in range(N+1)]
    dp(N)
    for _ in range(M):
        S, E = map(int, sys.stdin.readline().rstrip().split())
        print(table[S][E])