[백준] 10941 팰린드롬?

문제

• 홍준이가 자연수 N개를 칠판에 적고, 명우에게 질문을 M번 한다.
• 각 질문은 두 정수 S와 E로 나타낼 수 있고, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지 물어본다.
• 자연수 N개와 질문 M개가 모두 주어질 때, 명우의 대답을 구하는 프로그램 하기

 

• 1 <= N <= 2,000
  1 <= M <= 1,000,000

 

풀이

• N이 최대 2000개 이므로 모든 팰린드롬의 경우의 수 ( Nx(N+1)//2 )를 구해두기로 하자.
• 팰린드롬은 gap이 0일 때와 1일 때를 미리 구해둔다.
  • gap=0 ; 자기 자신이므로 항상 팰린드롬이다.
  • gap=1 ; nums[i] == nums[i+1] 이면 팰린드롬이다.
• 반복문을 돌면서 gap=2 ~ N+1 까지의 값을 구한다.

 

import sys
input = sys.stdin.readline

N = int(input())
nums = [0] + list(map(int, input().split()))

# 팰린드롬 구하기
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N):
    dp[i][i] = 1
    if nums[i] == nums[i+1] :
        dp[i][i+1] = 1
dp[N][N] = 1

for gap in range(2, N+1) :
    for s in range(1, N+1-gap) :
        if dp[s+1][s+gap-1] and nums[s] == nums[s+gap] :
            dp[s][s+gap] = 1

# 질문에 답변
for _ in range(int(input())) :
    S, E = map(int, input().split())
    print(dp[S][E])

 

References

• 백준 DP