[백준] 10943번: 팰린드롬? - C++

문제 출처:https://www.acmicpc.net/problem/10942

---

문제

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

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

각 질문은 두 정수 S와 E로 나타낼 수 있으며, 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을 출력한다.

문제를 처음 읽었을때 딱히 이해가 어렵지 않고 풀이 방법도 어렵지 않을 것 같습니다. 

그러나 문제를 풀어보기 시작하면 당연하게도 시간이 발목을 잡습니다. 

수열의 최대 크기가 2,000이고 질문의 개수가 최대 1,000,000 이므로 S,E가 주어졌을때 일일히 for문을 돌려가며 팰린드롬

을 판별하면 절대 제한 시간인 0.5초 안에 문제를 풀지 못합니다. 따라서 동적 계획법(다이나믹 프로그래밍)을 이용하여 O(n)

의 시간복잡도를 가지는 팰린드롬 계산을 최대한 O(1)로 만들어야 문제가 풀리게 됩니다.

그럼 이제 이 문제에 대하여 어떻게 동적 계획법을 적용하는지 설명 하겠습니다. 

핵심은 팰린드롬의 특징을 이용하는것인데 어떤 수열 N과 S,E가 주어졌을때 이 S,E가 팰린드롬이라면 S<=E라는 조건 안에

서 (S+1,E-1) (S+2,E-2) (S+3,E-3)....... 모두 팰린드롬이 된다는 것입니다. 

이 점을 이용하여 DP[2001][2001]배열을 하나 만든 뒤 S,E가 주어졌을때 팰린드롬이라면 DP[S][E], DP[S+1][E-1], DP[S+2][E-2]

DP[S+3][E-3]..... 전부 팰린드롬이라고 체크를 해준다면 나중에 이 범위에 속해있는 S,E가 주어졌을때 반복문을 돌리지 않고 

즉시 팰린드롬인지 아닌지 알 수 있게 됩니다.

그림으로 설명하면 다음과 같습니다.

수열 N과 S,E가 주어졌을때 S,E가 팰린드롬인지 구해주는 함수입니다.

반복을 모두 마치고 리턴하면 팰린드롬 중간에 반복이 중단되면 팰린드롬이 아닙니다.

 

int palindrome(int *arr, int s, int e) {
    while (s < e) {
        if (arr[s] == arr[e]) {
            s++; e--;
        }
        else {
            return 0;
        }
    }
    return 1;
}

전체 코드입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
 
using namespace std;
 
int DP[2001][2001];
 
int palindrome(int *arr, int s, int e) {
    while (s < e) {
        if (arr[s] == arr[e]) {
            s++; e--;
        }
        else {
            return 0;
        }
    }
    return 1;
}
 
int main(void)
{
    int n, m, s, e, *arr, *result;
        ;
    for (int i = 0; i < 2001; i++) {
        for (int j = 0; j < 2001; j++) {
            DP[i][j] = -1;
        }
    }
 
    scanf("%d", &n);
    arr = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    scanf("%d", &m);
    result = new int[m];
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &s, &e);
        s--; e--;
        //DP[S][E]가 -1이라면 아직 팰린드롬인지 모르는 상태이므로 팰린드롬을 계산한다.
        if (DP[s][e] == -1) {
            //주어진 S,E가 팰린드롬이라면 S,E사이의 수도 팰린드롬이므로 DP배열에 세팅해준다
            if (palindrome(arr, s, e)) {
                while (s < e) {
                    DP[s][e] = 1;
                    s++; e--;
                }
                result[i] = 1;
            }
            //S,E가 팰린드롬이 아니라면 DP[S][E]는 0으로 세팅
            else {
                DP[s][e] = 0;
                result[i] = 0;
            }
        }
        //DP[S][E]가 0이면 S,E는 팰린드롬이 아니다.
        else if (DP[s][e] == 0) {
            result[i] = 0;
        }
        //DP[S][E]가 1이면 S,E는 팰린드롬이다.
        else if (DP[s][e] == 1) {
            result[i] = 1;
        }
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", result[i]);
    return 0;
}