[Gold IV] 팰린드롬? - 10942 (dp)

[Gold IV] 팰린드롬? - 10942

문제 링크

성능 요약

메모리: 174360 KB, 시간: 920 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

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

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

 

풀이 방법

익숙해지지 않는 DP 문제.. 그러나, 풀이를 봐도 이해 안가는 DP 문제도 많이 봤지만, 이번 문제는 곧바로 이해가 될 정도이다.

첫 번째로, N만큼 2중 반복문(i, left)을 돌면서 양쪽을 비교하여 팰린드롬을 판단할 left와 right(left + i)를 설정한다. right가 left+i인 이유는 자기 자신의 숫자[0(left),0(right),(2,2) 등..]부터 시작하여 점점 한 칸씩 벌려가며 dp에 팰린드롬을 판단하고, 다음 칸을 비교하기 위함이다.

예외 처리(break if right >= N)를 해준 뒤, dp를 이용해 팰린드롬인지 판단하기 위한 3가지의 if문만 걸어주면 된다.

1. left와 right가 동일할 경우 : 모두 자기 자신인 한 숫자를 가리키므로, 무조건 팰린드롬이 되므로 해당 인덱스에 1 기록

2. 두 숫자가 서로 이웃해 있을 경우 : 이웃한 숫자가 같은 값을 가질 경우 팰린드롬이 되므로 해당 인덱스에 1 기록

3. 동일한 간격으로 서로 떨어진 두 숫자가 같을 경우 : dp로 팰린드롬을 판단하여 기록하는 방법을 한 칸씩 점점 벌리면서 기록했으므로 바로 이전에 기록했던 dp 인덱스의 값이 팰린드롬이어야 팰린드롬이 되므로 이 경우에만 해당 인덱스에 1 기록 (예를 들어, 12321이라는 숫자가 있고, 0번 째 인덱스와 4번 째 인덱스의 범위의 팰린드롬을 판단한다고 했을 때 0, 4번 째 인덱스가 값이 1로 같더라도, 그 전의 범위인 232, 3이 팰린드롬이 되어야함.)

4. 구하고자 하는 범위 출력

 

import sys
input =sys.stdin.readline
N = int(input())
arr =  list(map(int, input().split()))
dp = [[0] * N for _ in range(N)]

for i in range(N):
    for left in range(N):
        right = left + i
        
        if right >= N:
            break
            
        if left == right:
            dp[left][right] = 1

        elif left + 1 == right:
            if arr[left] == arr[right]:
                dp[left][right] = 1
        elif arr[left] == arr[right] and dp[left+1][right-1]:
            dp[left][right] = 1
for i in range(int(input())):
    x, y = map(int, input().split())
    print(dp[x-1][y-1])