[Python]동적계획법2 백준 10942

   문제

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

팰린드롬이란 반으로 나누어 좌우가 같은 것이다.

짝수개일때는 반으로나누어 같은경우 홀수개일때는 중앙값을 기준으로 좌우가 같은

것이다.

2 2, 4 4 4 4 , 1 ,1 2 1 같은경우 모두 팰린드롬이다.

테스트 케이스마다 모두 계산한다면 O(N^2)*M 번이 걸릴것이다.

dp를 이용해 모든 경우를 구한뒤 출력만 해주는 방식으로 구현해보자.

방법은 먼저 한자리 일때를 모두 1로 초기화 시켜주고 2자리 일때도 각각 구해주었다.

그뒤 하나씩 늘려가며 이전값들이 팬린드롬이면서 양끝값을 비교하여 같으면 팬린드롬

이고 이를 저장하여 다시 이용한다.

작은 예를 들어보자

num=[1,2,3,2,1] 이라는 배열이 주어졌을때 4*4의 dp를 만들어주고 초기화시킨다.

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

그뒤 0~1구간 0~2구간 0~3 구간 0~4구간 순으로 팬린드롬을 찾는다.

2자리까지는 이미 초기화할때 구해주었으므로 

0~2구간 부터 보자

dp[0][2]은 dp[1][1]=1이지만 num[0]과 num[2]은 다르기때문에 넘어가준다.

0~3 구간일때를 보자

dp[1][3]은 dp[2][2]=1이고 num[1]=num[3]이 같으므로 팬린드롬이다.

1 0 0 0 0

0 1 0 1 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

dp[0][3]은 dp[1][2]가 0이므로 아니다.

0~4구간

dp[2][4]는 dp[3][3]=1이고 num[2]와 num[4]는 다르기때문에 아니다

dp[1][4]은 dp[2][3]=0이므로 넘어가준다

dp[0][4]은 dp[1][3]=1이고 num[0]과 num[4]는 같으므로 팬린드롬이다.

 최종적으로 

1 0 0 0 1

0 1 0 1 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

이라는 결과를 얻을수 있다.

코드로 확인해보자.

import sys
 
 
N=int(sys.stdin.readline())
num_list=list(map(int,sys.stdin.readline().split()))
dp=[[0 for _ in range(N)] for _ in range(N)]
for i in range(N):#길이가 1일때
    dp[i][i]=1
    if i<N-1 and num_list[i]==num_list[i+1]:#길이가 2일때
        dp[i][i+1]=1
 
 
for i in range(1,N):
    for j in range(1,i+1):
        if num_list[i]==num_list[i-j] and dp[i-j+1][i-1]==1:
            dp[i-j][i]=1
 
M=int(sys.stdin.readline())
for _ in range(M):
    S,E=map(int,sys.stdin.readline().split())
    print(dp[S-1][E-1])