🥚문제

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

• 다이나믹 프로그래밍

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = [0] + list(map(int, input().split()))

# s~e까지의 숫자가 팰린드롬인지 확인하는 방법
# s번째 숫자 == e번째 숫자이고, s+1 ~ e-1의 숫자가 팰린드롬이면 팰린드롬
dp = [[1]*(N+1) for _ in range(N+1)]

# 1개
for i in range(1, N+1):
    dp[i][i] = 1

# 2개
for i in range(1, N+1):
    for j in range(i, N+1):
        if i + 1 == j:
            if arr[i] == arr[j]:
                dp[i][j] = 1
            else:
                dp[i][j] = 0

# 3개 이상
for x in range(2, N):
    for i in range(1, N+1):
        if i + x <= N:
            j = i + x
            if arr[i] == arr[j]:
                dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = 0

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

---

🧂아이디어

DP

• DP를 이용한 팰린드롬 판별법:
  • i ~ j까지의 수가 팰린드롬인가?
  • i번째 수와 j번째 수가 같고, i+1 ~ j-1번째 수 (사이의 수)가 팰린드롬이면 팰린드롬