백준_python 10942번 팰린드롬?(시간초과, DP)

<문제 링크>

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

10942번: 팰린드롬?

 

 

<정답 코드>

import sys
 
input = sys.stdin.readline
 
n = int(input())
list_n = list(map(int, input().split()))
m = int(input())
 
dp_table = [[0] * (n+1) for _ in range(n+1)]
 
for i in range(1,n+1):  
    dp_table[i][i] = 1     # 길이가 1이면 항상 펠린드롬
 
for i in range(1,n):
    if list_n[i-1] == list_n[i]:
        dp_table[i][i+1] = 1    # 길이가 2이면 두 요소가 같으면 펠린드롬
 
for cnt in range(2,n):          # 길이가 3이상이면
    for i in range(1, n-cnt+1):
        j = i + cnt
        if list_n[i-1] == list_n[j-1] and dp_table[i+1][j-1] == 1:
            dp_table[i][j] = 1    # 맨 앞뒤 값이 같고 그 사이가 펠린드롬이면 펠린드롬
 
for _ in range(m):
    s, e = map(int, input().split())
    print(dp_table[s][e])

 

DP(dynamic programming)으로 풀지 않으면 시간초과 발생

 

 

펠린드롬 여부를 사전에 판단해 dp_table에 저장해두고,

구하는 부분의 결과를 빠르게 반환하는 방법 사용 

 

dp_table 구현

 

 

한 범위의 펠린드롬 여부를 확인하기 위해 양 끝값과 그 사이의 페린드롬 여부를 확인한다는 점에서, 

작은 문제의 결과에 기반해 큰 문제를 판단하는 DP의 최적 부분 구조 특징을 활용한다.

 

 

리스트 슬라이싱 대비 장점

• 리스트 슬라이싱
  • 해당 구간 추출 및 역순으로 뒤집어 원본이랑 비교하는 시간 O(n) -> 시간초과
• DP
  • 모든 구간 미리 계산, 결과 출력에 걸리는 시간 O(1)