[다이나믹 프로그래밍] 10942번 - 팰린드롬?

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

(한줄평) 아이디어는 빨리 떠올렸지만 코드 짜는게 생각보다 오래걸렸던 문제다. 대각선 순서로 확인하는 코드 그냥 외우자.. 이상한데서 시간 낭비했다..

풀이 시간: 75분 이내

 

1) 문제 해결 아이디어

크기가 n인 수열과 m개의 시작점, 끝점(s, e)가 주어질 때 각 질문에 대한 팰린드롬 여부를 구하는 문제다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

(1 ≤ N ≤ 2,000, 1 ≤ N ≤ 2,000,  1 <= 수열의 수 <= 100,000)

펠린드롬이란 앞에서 읽든, 뒤에서 읽든 같은 단어를 말한다.

 

<경우의 수>

3가지 경우로 나눠볼 수 있다. 문제의 s, e 는 각각 i, j에 대응한다.

1) 원소가 1개일 경우(i, j가 같을 경우) 항상 펠린드롬이다.

2) 원소가 2개일 경우, i번째 원소와 j번째 원소의 값이 같기만 하면 펠린드롬이다.

3) 원소가 3개이상일 경우,

i번째 원소와 j번째 원소의 값이 같고 양쪽 원소를 제외한 (i+1) ~ (j-1) 번째까지 수가 펠림드롬이면 펠린드롬이다.

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 수열 크기
graph = list(map(int, input().split()))  # 크기가 n인 수열
m = int(input())  # 질문 개수
# d[i][j]: i~j번째까지 수의 펠린드롬 여부(1: 펠린드롬, 0: 아님)
d = [[0] * n for _ in range(n)]

for k in range(n):
  for i in range(n - k):
    j = i + k
    # 1. 원소가 1개면 항상 팰린드롬
    if i == j:
      d[i][j] = 1
    # 2. 원소 2개면 두 값이 같을 때만 팰린드롬
    elif j - i == 1:
      if graph[i] == graph[j]:   
        d[i][j] = 1
    # 3. 원소가 3개이상이면
    else:
      # 양쪽 끝값이 같고 가운데 부분이 펠린드롬이면 팰린드롬
      if d[i + 1][j - 1] == 1 and graph[i] == graph[j]:   
        d[i][j] = 1
    i += 1

for _ in range(m):
  s, e = map(int, input().split())  # s번째수, e번째 수
  print(d[s-1][e-1])