[C++] 백준 10942번 팰린드롬?

다이나믹 프로그래밍 문제입니다.

팰린드롬 = 뒤집어도 같은 문자
ex) 121, 1234321, 919, 111, 22, 3

숫자가 주어지고 범위가 주어졌을 때
팰린드롬인지 아닌지 출력하는 문제입니다.

모든 범위에 대한 팰린드롬의 결과를 미리 구합니다.
DP[x][y]는 x에서 y까지의 범위가 팰린드롬인지를 가지고 있습니다.

먼저 범위의 길이가 1과, 2에 대해서는 미리 구해줍니다.

for (int i = 1; i <= n; i++) { 
	DP[i][i] = 1; 
	if (arr[i] == arr[i - 1]) { 
		DP[i - 1][i] = 1; 
	} 
}

그리고 나머지 범위에 대해서 구합니다.

for (int i = 2; i < n; i++) {
	for (int j = 1; j <= n - i; j++) {
		int k = i + j;
		if (arr[j] == arr[k] && DP[j + 1][k - 1] == 1)
			DP[j][k] = 1;
	}
}

i = 범위
j = 탐색 시작위치
k = 탐색 끝 위치

작은 범위부터 점점 늘려가서 모든 범위에 대한 팰린드롬을 확인합니다.
팰린드롬일 경우 1을 입력하고 아닐경우 0을 입력하여서 결과값을 저장합니다.

#include <iostream>
#include <cstring>
using namespace std;

int arr[2010];
int DP[2010][2010];

int main(int argc, char *argv[]){
	int n;

	cin >> n;

	memset(arr, 0, sizeof(arr));
	memset(DP, 0, sizeof(DP));

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &arr[i]);
	}

	for (int i = 1; i <= n; i++) { 
		DP[i][i] = 1; 
		if (arr[i] == arr[i - 1]) { 
			DP[i - 1][i] = 1; 
		} 
	}

	for (int i = 2; i < n; i++) {
		for (int j = 1; j <= n - i; j++) {
			int k = i + j;
			if (arr[j] == arr[k] && DP[j + 1][k - 1] == 1)
				DP[j][k] = 1;
		}
	}

	int q;
	scanf("%d", &q);

	for (int i = 0; i < q; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", DP[x][y]);
	}

	return 0;
}