[DP] BOJ 10942 팰린드롬?

문제

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

10942번: 팰린드롬?

 

풀이

DP 테이블 정의까지는 생각했으나 점화식을 찾지 못했다.

0부터 찾아가는게 아닌 N부터 점차 찾아오는 식으로 풀이해야한다.

 

우선 팰린드롬의 특징부터 살펴보자

1. 팰린드롬은 거꾸로 해도 원본과 같은 수열을 이룬다 (테넷)

2. 팰린드룸은 양끝의 값이 같다.

3. 팰린드룸은 양끝을 제외한 나머지 수열도 대칭을 이룬다. (1번과 같다)

4. 수열의 길이가 2일 때는 2번만 고려한다.

 

DP로 풀 수 있는 힌트는 3번에 있다.

아래 표는 행의 숫자부터 열의 숫자까지 팰린드룸인지 아닌지 체크하는 표다.

 

행을 i, 열을 j 라고 했을때, 위 테이블은 다음과 같은 논리로 진행된다.

 

1. i == j 일 때는 길이가 1인 수열 이므로 무조건 팰린드룸이다.

2. i+1 == j 일 때는 길이가 2이므로 두 수가 같다면 팰린드룸이다.

3. 이외의 경우에는 수열의 처음과 끝이 같고, 그 안의 수열이 팰린드룸이라면 해당 수열은 팰린드룸이다.

 

이제 위 논리와 같이 가장 마지막 요소부터 테이블을 채워보자

 

우선 1번 논리에 따라서 i == j 이므로 해당 수열은 팰린드룸이다.

 

그 다음은 2번 논리에 따라서 i+1 == j 일 때, 길이가 2이므로 두 수가 같다면 팰린드룸이다. 하지만 예제에서는 두 수가 다르므로 팰린드룸이 될 수 없다.

 

다음은 3번 논리에 따라서 처음과 끝이 같고 그 안의 수가 팰린드룸이라면 해당 수열은 팰린드룸이다.

우선 i = 5, j = 7 일 때, 처음과 끝은 1로 같은 수이다. 그리고 2는 이미 이전 테이블을 만들 때 1번 논리에 의해서 팰린드룸이라는 것을 알고 있다. 그러므로 5에서 7의 수열은 팰린드룸이라고 할 수 있다.

 

위를 반복하여 테이블을 채워 나가자. 그렇다면 다음과 같은 테이블이 만들어진다.

 

코드

import sys

N = int(sys.stdin.readline())

num_list = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())

my_list = [[0] * N for _ in range(N)]

my_list[N-1][N-1] = 1

for i in range(N-1,-1,-1):
    for j in range(N-1,i-1,-1):
        if i >= N-1 : 
            continue

        if i == j : # 논리1
            my_list[i][j] = 1
        elif i+1 == j : # 논리2
            my_list[i][j] = 1 if num_list[i] == num_list[j] else 0
        else: # 논리3
            my_list[i][j] = 1 if my_list[i+1][j-1] and num_list[i] == num_list[j] else 0

    
for _ in range(M):
    S, E = map(int,sys.stdin.readline().split())

    print(my_list[S-1][E-1])