[백준] 10942(파이썬) - 팰린드롬?

 

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

10942번: 팰린드롬?

• 이 문제를 읽고 든 생각은 1000000... 2000....? 무조건 시간 초과가 안 걸려야겠구나 였습니다.
• 시간 초과를 해결하면서 생각할 수 있는 해법은 DP를 이용한 풀이였습니다.
• 일단 팰린드롬이 되기 위한 조건을 생각해봅시다.
  • 일단 숫자 하나는 무조건 팰린드롬이 됩니다.
  • 숫자 2개일 경우, 숫자가 같으면 팰린드롬이 됩니다.
  • 숫자가 3개일 경우 양 끝 값이 같으면 팰린드롬이 됩니다.
• 그리고 공통적으로 생각 할 수 있는 조건은 양끝 값이 무조건 같아야 확인해볼 가치(?)가 있다는 것입니다.
• 그래서 로직을 다음과 같이 생각해봤습니다.
  • dp 테이블을 만들고,
  • n개의 숫자를 받은뒤, for문을 돌리면서 첫 값과 끝 값의 인덱스를 dp테이블에 1로 저장해둡니다.
  • 만약에 비교하고자 하는 첫 인덱스가 끝 인덱스가 같으면 dp [첫 인덱스][끝 인덱스] = 1을 넣어줍니다.
  • 다를 경우, 첫 인덱스의 값과 끝 인덱스의 값을 비교해서 같을 때,
    만약에 붙어 있는 자리일경우 (두 자리인데 같을 경우) 에는 dp 테이블에 1을 넣어줍니다.
  • 마지막으로 첫 인덱스의 값과 끝 인덱스의 값을 비교해서 같을 때,
    dp [첫 인덱스의 다음 값][끝 인덱스의 이전 값] 이 1일 경우, ( 양끝 값을 제외한 내부 숫자들이 팰린드롬일 경우) 
    dp 테이블에 1을 넣어줍니다.(팰린드롬 처리를 해줍니다.)

import sys
from typing import List
input = sys.stdin.readline

n = int(input())
data = list(map(int,input().split()))
m = int(input())
dp = [[0] * (n+1) for _ in range(n+1)]

for number in range(n):
    for s in range(n-number):
        e = s + number
        if s == e :
            dp[s][e] = 1
        elif data[s] == data[e]:
            if s + 1 == e :
                dp[s][e] = 1
            elif dp[s+1][e-1] == 1:
                dp[s][e] = 1

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