[BOJ/백준] 21925 짝수 팰린드롬

import sys

def check(idx,cnt):
    global result
    if idx == N:
        result = max(result,cnt)
        print(result)
        exit()
        return
    else:
        for next_idx in range(idx+1,N,2):
            if dp[idx][next_idx]:
                check(next_idx+1,cnt+1)
input = sys.stdin.readline

N = int(input())

arr = list(map(int,input().split()))

dp = [[ True  if i == j else False for j in range (N)]  for i in range(N)]
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = True

for i in range(2,N):
    for j in range(N-i):
        if arr[j] == arr[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = True

max_num = N//2
result = -1
check(0,0)
print(result)

이 문제는 boj.kr/10942에서 풀었던 전체 배열에 대한 팰린드롬의 dp를 구해놓은 상태로 풀었다.

 

먼저 전체 배열의 대한 팰린드롬 상태를 dp에 저장시켜놓는다.

 

그리고 우리는 check를 해주면 된다.

 

우리는 짝수개 만큼 나눌수 있다.

 

그러면 우리는 현재 위치에서 짝수번째 떨어진 위치의 dp 상태값을 통해 팰린드롬이면 재귀를 통해

 

N번째 index에 도착할때까지 계속해준다.

 

그리고 최초로 도착을 했을때가 가장 최대 짝수팰린드롬이므로, 그때 값을 출력해주면 된다.

 

왜냐하면, 우리는 2칸단위부터 자르기 때문에,

 

가장 먼저 도착하는 것이, 가장 많이 자른것이기 때문이다.

 

이 문제는 이렇게 dp로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,

 

그 풀이는 정확히 이해하지 못했다.