문제
접근
DP 문제이다.
start에서 end까지의 팰린드롬 여부는
DP(start, end) = 0 or 1 이다.
start에서 end까지의 수가 팰린드롬을 이루기 위한 재귀적 조건은 다음과 같다.
arr[start] == arr[end] and DP(start+1, end-1)
bottom-up 방식으로 할까하다가, top-down 방식을 연습해보려고 top-down으로 풀었다.
dp에 값이 저장되어 있으면 dp값을 출력하면 되고,
아직 저장이 안되어 있으면, 재귀적으로 값을 구해준다.
재귀 호출 때문에 런타임에러가 발생해서 늘려줬다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split(' ')))
dp = [[-1] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
m = int(input())
def findDP(start, end):
if start > end:
return 1
if dp[start][end] != -1:
return dp[start][end]
if arr[start] == arr[end]:
dp[start][end] = findDP(start+1, end-1)
else:
dp[start][end] = 0
return dp[start][end]
for _ in range(m):
start, end = map(int,input().split(' '))
if dp[start-1][end-1] == -1:
dp[start-1][end-1] = findDP(start-1, end-1)
print(dp[start-1][end-1])