[Python] BOJ no.10942 팰린드롬?

문제 링크

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

10942번: 팰린드롬?

---

문제 설명

팰린드롬은 문자열이나 수열의 앞뒤가 동일한 형태를 말한다. 예를 들면, 기러기, 토마토, 12321 같은 것들이 될 수 있겠다. 이 문제에서는 수열이 주어지고 임의의 인덱스가 주어지면 팰린드롬인지 맞춰야한다. 다만 프로그램이 돌아가는 시간을 많이 주지 않기 때문에 DP(다이내믹 프로그래밍)를 사용해서 풀어야한다.

---

내 풀이

뭔가.. 2차원 DP 공간을 생성해서 풀어야겠다는 생각까지는 도달했지만 어떻게 DP 로직을 쌓을지는 생각나지 않았다...후..ㅜㅜ

결국 실질적인 답에 연결되는 로직은 구현하지 못했고 다른 분들의 로직을 대충만 보고 구현해보자! 라고 생각했다.

---

풀이 #1

import sys
input = sys.stdin.readline
n = int(input())
ls = list(map(int, input().split()))
m = int(input())

d = [[0] * n for _ in range(n)]
for i in range(n):
  d[i][i] = 1

# 2개 짜리 팰린드롬 검사
if len(ls) > 1:
  for i in range(n-1):
    if ls[i] == ls[i+1]:
      d[i][i+1] = 1
if len(ls) > 2:
  for i in range(3, len(ls)+1):
    for j in range(n-i+1):
      if ls[j] == ls[j+i-1] and d[j+1][j+i-2] == 1:
        d[j][j+i-1] = 1

for _ in range(m):
  start, end = map(int, input().split())
  print(d[start-1][end-1])

위는 내가 푼게 맞긴 맞다.. 다만 아이디어는 생각나지 못해 C++로 된 로직을 참고했다..(패배..)

로직은 다음과 같다.

1. 먼저 DP공간의 1개짜리 수열에 대해 팰린드롬을 검사한다. (당연히 1개짜리니 팰린드롬일 것이다.)
2. 2개짜리 수열의 팰린드롬을 검사한다. (3번부터 나오겠지만 가운데에 있는 수열이 팰린드롬인지 알아야하기 때문에 2개짜리 수열까지는 따로 검사하는 것, 그래서 3개짜리 수열부터 모듈화해서 팰린드롬 검사가 가능)
3. 3개짜리부터 for loop을 돌린다. -> 이 때 수열의 start와 end가 같은지 + DP공간의 start+1, end-1에서 팰린드롬 검사한 결과가 팰린드롬이 맞는지 확인한다.

안쪽의 수열이 이전에 검사했을 때 팰린드롬이라면 새로 들어오는 끝과 끝이 같은 값을 가질 때 반드시 팰린드롬이다.