189. 10942(팰린드롬?) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())
board = list(input().split())
M = int(input())
dp = [[0]*N for _ in range(N)]
result = []

for i in range(N):
    dp[i][i] = 1

for i in range(N-1):
    if board[i] == board[i+1]:
        dp[i][i+1] = 1

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

for i in range(M):
    S, E = map(int, input().split())
    result.append(str(dp[S-1][E-1]))

print("\n".join(result))

문제요약

범위의 시작이 S, 끝이 E가 팰린드롬이라면 1 아니라면 0을 출력하라 

설명

팰린드롬이란 똑바로읽어도 거꾸로읽어도 같은것을 말한다.

(기러기, 토마토, 스위스, 인도인, 별동별, 역삼역)

 

팬린드롬은 다음과 같은 조건에 만족한다.

 

1. 길이가 1일 경우

길이가 1이라는 것은 예를들어 별 같은 경우 앞으로 읽어도 별 뒤로 읽어도 별이기 때문에 팰린드롬이다.

for i in range(N):
    dp[i][i] = 1

 

2. 길이가 2인데 맨 앞과 맨 뒤가 값이 같을 경우

시작과 끝의 값이 같을 경우 예를들어 별별 같은 경우 맨앞이 별 맨뒤가 별이기 때문에 팰린드롬의 조건에 만족한다.

for i in range(N-1):
    if board[i] == board[i+1]:
        dp[i][i+1] = 1

 

3. 길이가 3 이상일때.

길이가 3 이상일 때에는 두가지 조건이 만족해야한다.

1) 시작과 끝의 값이 같을 경우

2) 시작과 끝점을 제외한 사이의 값들이 팰린드롬일 경우

 

1) 은 쉽게 구할 수 있다.

board[j] == board[i+j]

 

하지만 2)는 어떻게 구하느냐?

2) 같은 경우에는 사실 사전에 미리 구했다.

예를들어 1 2 1인 경우, 1)은 바로 만족하는 것을 알 수 있다.

그럼 2는 어떻게 팰린드롬인지를 아느냐? 우리가 조건 1(길이가 1일 경우)로 이미 2는 팰린드롬이라는 것을 구했다.

때문에 1) 2)를 합쳐 다음과 같이 구할 수 있다. 

        if board[j] == board[i+j] and dp[j+1][i+j-1] == 1:

 

이 조건에 만족하는 경우 

	dp[j][i+j] = 1

해당 경로에 1을 저장한다.

이렇게 하면 

이 예제의 경우 dp는 다음과 같은 값을 가지게 될 것이다.

간단히 정리해보면, 대각선 기준으로 윗부분만을 사용하게 되고,

대각선은 무조건 1이 나올 것이며 (조건 1을 만족)

대각선 바로 위는 조건2에 따라1과 0이 나오게 된다.

그리고 나머지

부분은 조건 3에 따라 결과가 나올 것이다.

 

때문에 

for i in range(2, N):
    for j in range(N-i):

반복문의 첫부분을 다음과 같이 작성한 것이다.