BOJ(팰린드롬)(10942)

작성일 | In

팰린드롬? (10942)

시간초과

  • DP로 어떻게 풀지 감이 안와, 그냥 풀었더니 시간초과가 떴다.

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
for i in range(m):
    a, b = map(int, input().split())
    temp = arr[a-1:b]
    t = len(arr[a-1:b])//2
    for i in range(t):
        if temp[i] != temp[-1]:
            print(0)
            break
    else:
        print(1)
  • 직접 뒤집어보는 방법 -> 어떤 문자열 s가 팰린드롬인지 확인하는데 걸리는 시간 O(N)
  • 팰린드롬의 정의처럼 쌍을 이루는지 확인해보는 방법 -> 이 방법도 O(N)
  • 어떤 수열의 연속하는 부분 수열이 팰린드롬인지 아닌지 확인하는 문제
  • 질문이 M개면 O(MN)이라는 시간이 걸림.
  • 이 방법으론 해결할 수 없다.

풀이방법

  1. 길이가 1인 문자열은 항상 팰린드롬이다. D[i][j] = True
  2. D[i][j] = A[i] ~ A[j]까지가 팰린드롬이면 1, 아니면 0으로 정의, 답을 채우지 않았으면 -1이 들어가 있는 배열
  3. 길이가 2인 문자열은 ? -> True인 경우는 A[i] == A[i+1]인 경우 다르면 False
  4. 길이가 3이상인 경우에는 재귀적인 식을 만들 수 있다.
      1. A[i] == A[j]
      1. A[i+1] == A[j-1]
    • 즉 첫 글자와 마지막 글자가 같고 이 사이에 D[i+1][j-1]이 팰린드롬이어야 한다.
    • 즉 모든 정보를 DP에 이미 담은 뒤 나올 때만 맞게 인덱스 처리해서 보여주면 된다.
  • 문자열의 길이가 이 문제의 크기가 된다.
  • bottom up으로 풀고 싶다면, 길이가 1인 것부터 채운다. 길이를 기준으로 문제를 푼다.
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
d = [[0]*n for _ in range(n)]

for i in range(n):
    d[i][i] = True  # 길이가 1인 문장은 항상 팰린드롬이다.
for i in range(n-1):  # 길이가 2인 문장 중 같으면 팰린드롬이다
    if a[i] == a[i+1]:
        d[i][i+1] = True
for k in range(3, n + 1):
    for i in range(0, n-k+1):
        j = i+k-1
        if a[i] == a[j] and d[i+1][j-1]:
            d[i][j] = True
m = int(input())
for _ in range(m):
    s, e = map(int, input().split())
    print(1 if d[s-1][e-1] else 0)
  • 인강을 들어도 어려운 문제였다.

참고자료 codeplus

0%