[백준/파이썬] 10942번 팰린드롬?

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

10942번: 팰린드롬?

이 문제가 왜 DP를 이용하는지에 대한 이해를 도와주는 그림이다.

start와 end가 같을 때, list[start+1, end-1]이 이미 팰린드롬이라면 list[start,end]가 팰린드롬인지 아닌지 바로 판별할 수 있기 때문이다.

1. 우선 dp 테이블을 하나 정의한다. ex) dp[i][j], i는 start를 의미하고 j는 end를 의미한다

2. 길이가 1짜리인 리스트 (= i와 j가 동일한) 는 모두 팰린드롬이다

3. 길이가 2짜리 리스트는 만약 두 수가 동일하다면 팰린드롬이고, 그렇지 않다면 팰린드롬이 아니다.

 

4. 우리는 dp 테이블을 [1,3] [2,4] [3,5] ,, [1,4] [2,5] [3,6] ,,, [1,5] [2,6] [3,7] ,,, 이렇게 어떤 간격을 가진 범위부터 채워나가야한다.

[1,3], [1,4] [1,5] 이런 식으로 채우면 [1,5]를 검사할 때 아직 채우지 못한 [1+1][5-1]에 대한 정보를 채우지 못하기 때문이다!

 

두번째 for문을 i로 잡고, j는 i+1+cnt로 선언해준다. 여기서 cnt는 앞서 말한 간격을 조정해주는 변수이다!

간격이 리스트의 길이가 될 순 없으므로 n-2까지만 검사해야하며,  i는 시작점이기 때문에 (리스트 길이 - 간격)까지만 돌려주면 된다.

import sys
#from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

if __name__ == "__main__":
  n = int(input())
  numbers = [0] + list(map(int, input().split()))
  dp = [ [False for _ in range(n+1)] for _ in range(n+1)]
  
  
  for i in range(1,n+1): # [1,1] [2,2] 같은 경우는 항상 펠린드롬!
      dp[i][i]=True
      
  for i in range(1,n): # [1,2] 같은 경우 같으면 회문
      if numbers[i]== numbers[i+1] : dp[i][i+1]=True
  
  for cnt in range(1,n-1):
    for i in range(1, n-cnt):
      # [1,3] [2,5]같은 경우
      j = i+1+cnt
      if numbers[i] == numbers[j] and dp[i+1][j-1]:
        dp[i][j] = True
      
  m = int(input())
  for i in range(m):
    s,e = map(int, input().split())
    if dp[s][e]:
      print(1)
    else: print(0)