(c++)백준 10942번: 팰린드롬?

acmicpc.net/problem/10942

10942번: 팰린드롬?

[풀이]

팰린드롬이란 수열이 거꾸로 했을 때도 같은 수열인 경우를 말한다.

가장 작은 단위의 수열(1개)부터 범위를 늘리면서 팰린드롬 여부를 판단하는 DP를 사용하였다.

DP[i][j]: S가 i이고 E가 j일 때 팰린드롬인지 여부

DP[i][i] = 1

if Num[i]==Num[j] : DP[i][i+1]=1

DP[i][j] = DP[i+1][j-1] && Num[i] == Num[j]

※cin, cout을 사용하면 시간초과가 나므로 scanf, printf 사용!

 

#include <iostream>
#include <cstring>
#define Max 2001
using namespace std;

int N, M;
int Num[Max];
int DP[Max][Max] = { 0, };

void solution() {
	for (int i = 1; i <= N - 1; i++) {
		DP[i][i] = 1;
		if (Num[i] == Num[i + 1])
			DP[i][i + 1] = 1;
	}
	DP[N][N] = 1;
	if (N == 1 || N == 2)
		return;
	for (int d = 2; d <= N - 1; d++) {
		for (int i = 1; i + d <= N; i++) {
			int j = i + d;
			if (DP[i + 1][j - 1] == 1 && Num[i] == Num[j])
				DP[i][j] = 1;
		}
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &Num[i]);
	}
	solution();
	scanf("%d", &M);
	int S, E;
	for (int i = 1; i <= M; i++) {
		scanf("%d %d", &S, &E);
		printf("%d\n", DP[S][E]);
	}
	return 0;
}