10942번 팰린드롬?

문제

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

접근 방식

쿼리 개수 m이 최대 1,000,000기 때문에 그때그때 팰린드롬인지 확인하는 Brute force 방식으로는 해결할 수 없다.

모든 부분 문자열에 대해 캐싱을 해두고 팰린드롬인지 확인하는 게 시간적으로 효율적이다.

이차원 DP로 표현하면 된다.

- dp[s][e]: s부터 e까지 부분 문자열이 팰린드롬인지

전체 점화식을 적어보면 다음과 같다:

- dp[s][e] = dp[s+1][e-1] AND numbers[s] == numbers[e]
- s == e 면 dp[s][e] = True
- s - e == 1 면 numbers[s] == numbers[e]

코드

import sys
input = sys.stdin.readline


n = int(input())
numbers = list(map(int, input().split()))

dp = [[False] * n for _ in range(n)]
for jump in range(n):
    for s in range(n):
        e = s + jump

        if e >= n:
            break

        if e == s:
            dp[s][e] = True
            continue

        if e - s == 1:
            dp[s][e] = True if numbers[s] == numbers[e] else False
            continue

        dp[s][e] = dp[s+1][e-1] and numbers[s] == numbers[e]


m = int(input())  # 쿼리 개수
for _ in range(m):
    s, e = map(int, input().split())
    # 팰린드롬 확인
    print(int(dp[s-1][e-1]))