[BOJ] 펠린드롬?

---

코드

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split()))
m = int(input())

num.insert(0, 0)

dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, i+1):
        if i == j: dp[i][j] = 1
        if i-j == 1 and num[i] == num[j]: dp[i][j] = 1
        if i-j >= 2 and num[i] == num[j] and dp[i-1][j+1] == 1: dp[i][j] = 1

for _ in range(m):
    s, e = map(int, input().split())
    print(dp[e][s])

결과

풀이 방법

• 다이나믹프로그래밍을 활용하여 해결하였다.
• DP[S][E] = S번째에서 E번째까지가 펠린드롬이면 1, 아니면 0으로 표기한다
• S번째에서 E번째까지가 펠린드롬이려면 먼저 DP[S+1][E-1] == 1이어야 하고, S번째 수와 E번째 수가 같아야 한다.
• 만약 |S-E| == 1 이면 두 수가 같은지만 확인하면 되고, S == E이면 항상 펠린드롬이다.

---