백준 10942번 펠린드롬?

백준 10942 펠린드롬?

문제 바로가기

코드

import sys

def palindrome(S, E):

  if check[S][E] == 1:
    return 1
  
  if S == E:
    return 1
  if E - S == 1:
    if numbers[S] == numbers[E]:
      check[S][E] = 1
      return 1
    else:
      return 0 
  
  if palindrome(S+1, E-1) == 1:
    if numbers[S] == numbers[E]:
      check[S][E] = 1
      return 1
    else:
      return 0
  else:
    return 0

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
questions = []

check = [[0 for _ in range(N)] for _ in range(N)]

for i in range(M):
  questions.append(list(map(int, sys.stdin.readline().split())))

for S, E in questions:
  print(palindrome(S-1, E-1))

문제 해결

펠린드롬이란?

palindrome : 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

❌ 각각의 자리수를 모두 비교한다.

주어진 질문에 따라서 각각 대답을 모두 해주면 된다. 이때 질문에 들어온 것을 기준으로 각각 S, E를 선택하고 펠린드롬을 만드는지 비교해주면 된다.

하지만 바로 시간초과..

주어지는 최대 질문의 개수가 1,000,000개이며 각각을 매번 모두 비교할 경우에는 시간 복잡도가 커지기 때문에 시간초과가 나는게 당연하다.

⭕️ DP를 이용한다.

시간을 줄이기 위해서는 이전에 했던 계산이 반복되지 않고 저장했다가 이용하면 된다. 여기서 펠린드롬을 증명하기 위해서는 각 S, E에서 한 칸씩 이동한 S+1, E-1 또한 펠린드롬을 이루어야 한다. 이를 바탕으로 다이나믹 프로그래밍 알고리즘을 이용하여 문제를 해결하면 쉽다.

이때 펠린드롬을 구하기 위해서 이전에 했던 계산이 있다면.. Check 이중 배열을 통해서 펠린드롬이 가능한지 확인하고 가능하다면 계산을 더 하지 않고 1을 반환하도록 했다.