[백준] 10942번 팰린드롬

10942 팰린드롬

문제

---

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 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을 출력한다.

---

풀이)

질문이 100만개라서, 일일히 범위 내의 수열 앞과 뒤 하나씩 확인하기엔 시간초과가 일어난다.

dp를 사용해서 풀어야하는 문제이다.

점화식은 아래와 같다

dp[s][e] = 시작위치 s부터 마지막 위치 e까지 수열이 펠린드롬일 경우 1 아니면 0

s와 e사이의 길이를 하나씩 늘리면서 memoization해주면 된다.

즉, 길이가 증가하면 

첫번째 숫자와 마지막 숫자가 같은지 확인 & 그사이 숫자들은 배열에 저장된 값이 1인지(=펠린드롬인지) 확인을 통해

펠린드롬인지 아닌지 확인하면 된다.

예시)

1 2 1 3 1 2 1 일때, 인덱스는 1부터 시작

s~e 길이 1 -> 무조건 펠린드롬

1 2 1 3 1 2 1 : dp[1][1] = 1

1 2 1 3 1 2 1 : dp[2][2] = 1

...        

s~e 길이 2 -> 두 숫자가 같으면 펠린드롬

1 2 1 3 1 2 1 : 1 != 2 따라서 dp[1][2] = 0

1 2 1 3 1 2 1 

1 2 1 3 1 2 1 

...

s~e 길이 3 -> 첫번째 숫자와 마지막 숫자가 같고, 중간 숫자들이 펠린드롬이면 펠린드롬 

  *2가지 조건을 모두 만족해야함

  (여기서는 중간숫자가 1개뿐이라 길이1이니깐 중간은 무조건 펠린드롬)

1 2 1 3 1 2 1 : 첫번째(1)와 마지막 숫자(1) 같음 & dp[2][2] = 1 => 펠린드롬 따라서 dp[1][3] = 1

1 2 1 3 1 2 1 : 첫번째(2)와 마지막 숫자(3) 다름 & dp[3][3] = 1 => 펠린드롬 x 따라서 dp[2][4] = 0

1 2 1 3 1 2 1 

1 2 1 3 1 2 1 

...

s~e 길이 4 -> 첫번째 숫자와 마지막 숫자가 같고, 중간 숫자들이 펠린드롬이면 펠린드롬

1 2 1 3 1 2 1 : 첫번째(1)와 마지막 숫자(3) 다름 & dp[2][3] = 0 => 펠린드롬 x 따라서 dp[1][4] = 0

1 2 1 3 1 2 1 : 첫번째(2)와 마지막 숫자(1) 다름 & dp[3][4] = 0 => 펠린드롬 x 따라서 dp[2][5] = 0

1 2 1 3 1 2 1 

1 2 1 3 1 2 1 

s~e 길이 5 

1 2 1 3 1 2 1 : 첫번째(1)와 마지막 숫자(1) 같음 & dp[2][4] = 0 => 펠린드롬 x 따라서 dp[1][5] = 0

1 2 1 3 1 2 1  : 첫번째(2)와 마지막 숫자(2) 같음 & dp[3][5] = 1 => 펠리드롬 따라서 dp[2][6] = 1

...

위의 예시처럼 배열을 채우면 된다.

1. s~e 사이의 길이가 1일 경우 : s = e 이므로 무조건 펠린드롬

2. s~e 사이의 길이가 2일 경우 : s, s+1 = e 이므로 s == e여야 펠린드롬

3. s~e 사이의 길이가 3이상일 경우 : s == e && s+1과 e-1사이가 펠린드롬이여야 펠린드롬

초기에 배열을 다 채워놓고, 질문에 대한 답을 출력할시에는 dp[s][e]를 출력하면 된다.

코드)

#include <stdio.h>
using namespace std;
 
int n, m;
int dp[2001][2001];//dp[s][e] = s부터 e까지 펠린드롬일 경우 1 아니면 0
int arr[2001];
int main() {
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    //한 글자는 무조건 펠린드롬
    for (int i = 1; i <= n; i++)dp[i][i] = 1;
    //두 글자는 두 수가 같아야 펠린드롬
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i + 1]) dp[i][i + 1] = 1;
    }
    //세 글자 이상부터
    for (int len = 2; len < n; len++) {
        for (int s = 1; s + len <= n; s++) {
            int e = s + len;
            //양 끝이 같고, 가운데 범위가 펠린드롬인 경우가 펠린드롬
            if (arr[s] == arr[e] && dp[s + 1][e - 1]) dp[s][e] = 1;
        }
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", dp[a][b]);
    }
    return 0;
}