팰린드롬? [백준 10942] - python

import sys
input = sys.stdin.readline

def BOJ10942() :
  n = int(input())
  l = list(map(int, input().split()))
  m = int(input())
  dp = [[0 for _ in range(n)] for _ in range(n)]

  for diff in range(n) :
    for start in range(n - diff) :
      end = start + diff
      
      if start == end :
        dp[start][end] = 1
        continue
      
      if start + 1 == end :
        if l[start] == l[end] : dp[start][end] = 1
        else :
          dp[start][end] = 0
        continue

      if l[start] == l[end] and dp[start+1][end-1] == 1 :
        dp[start][end] = 1
      else :
        dp[start][end] = 0

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

BOJ10942()

 

접근방법 :

1. 1213121이 주어졌을때 해당 숫자가 팰린드롬인지 어떻게 알 수 있을까요???

 

=> 21312가  팰린드롬인지 확인하고 양끝 숫자가 같은지를 파악하면 됩니다.

     

•    1213122 는 21312가 팰린드롬이지만 양 끝의 숫자가 다르기 때문에 팰린드롬이 아닙니다.

 

21312가 주어졌을 때 해당 숫자가 팰린드롬인지 어떻게 알 수 있을까요??

 

=> 131이 팰린드롬인지 확인하고 양끝 숫자가 같은지를 파악하면 됩니다. => 팰린드롬이네요

 

2. 1번의 규칙을 구현하기 위해 dp를 이용하였습니다. dp[s][e] 배열은 s부터 e까지의 문자가 팰린드롬인지 아닌지를 가지고 있는 배열입니다.

 

 

탐색은 위의 사진과 같이 진행해줍니다. dp[s][e]를 구할때 dp[s+1][e-1]을 이용하기 위함입니다.

 

3. 몇가지 조건을 설정해 볼게요 (시작점을 s, 끝점을 e로 지칭하겠습니다)

1. s와 e가 같으면 문자는 1자리가 되므로 팰린드롬입니다.
2. s와 e가 1이 차이가 나면 서로 같은 문자열이면 팰린드롬, 아니면 팰린드롬이 아닙니다.
3. s와 e가 2이상 차이가 날때는 s, e 각 인덱스의 문자가 같은지 비교하고 dp[s+1][e-1]이 팰린드롬인지 확인하면 됩니다.
   3번에서 비교하는 두개의 비교문이 true일때 dp[s][e]는 팰린드롬이 됩니다.

 

 

 

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

10942번: 팰린드롬?