[알고리즘] 10942번: 팰린드롬? Python 풀이

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

10942번: 팰린드롬?

입출력을 꼭 sys.stdin.readline 으로 바꿔주어야 시간초과가 안난다 !! 그리고 pypy3로 통과했다 

i 부터 j 까지의 수열이 펠린드롬인지 확인해야 하는데 미리 dp 테이블을 채워준다. 

펠린드롬 수열의 경우 길이가 1인경우 펠린드롬이므로 dp[i][i] = 1 을 채워준다. 

if start == end: # 자기 자신인 경우 무조건 1 임
    dp[start][end] = 1

 

길이가 2인경우 수열 두가지만 확인하면 되는데, 수열의 맨 앞 숫자인 numbers[start] 와 맨 뒤 numbers[end] 가 같은 경우 -> start 인덱스 바로 다음이 end인지 확인하면 된다. 

elif numbers[start] == numbers[end]:
    if start+1 == end: # 현재 수열의 길이가 2인경우 확인은 여기서 끝남
        dp[start][end] = 1

다음으로 저장되어 있는 dp 값을 이용해야 하는데, 수열의 맨 앞 start가 가리키는 numbers[start] 와 맨 뒤 numbers[end] 가 같은 경우, 길이가 앞뒤로 1씩 짧은 수열이 펠린드롬이었는지 확인하고, 펠린드롬이면 길이가 앞뒤로 1씩 늘어난 지금의 수열도 펠린드롬이다 

elif dp[start+1][end-1] == 1: # 현재 확인중인 start, -- 수열 -- ,end 에서
    dp[start][end] = 1 # 수열 부분도 펠린드롬인지 dp 저장된 값으로 확인하기

 

전체 코드

import sys 
input = sys.stdin.readline 

n = int(input())
numbers = list(map(int, input().split()))
m = int(input())

dp = [[0] * n for _ in range(n)]

for length in range(n):
    for start in range(n-length):
        end = start + length
        if start == end: # 자기 자신인 경우 무조건 1 임
            dp[start][end] = 1
        elif numbers[start] == numbers[end]:
            if start+1 == end: # 현재 수열의 길이가 2인경우 확인은 여기서 끝남
                dp[start][end] = 1
            elif dp[start+1][end-1] == 1: # 현재 확인중인 start, -- 수열 -- ,end 에서
                dp[start][end] = 1 # 수열 부분도 펠린드롬인지 dp 저장된 값으로 확인하기


for i in range(m):
    s, e = map(int, input().split())
    print(dp[s-1][e-1])