BOJ 10942 - 팰린드롬? (dp)

https://www.acmicpc.net/problem/10942

 

<문제설명>

숫자 배열 (최대 2000자)이 주어질 때 a[i]~a[j] (i,j)가 팰린드롬 수열인지 물어보는 최대 100만 쿼리에 답하는 문제.

 

<풀이>

f(i,j) : i~j번 수열이 팰린드롬인지?

위와 같은 점화식을 쓸 수 있다.

 

f(i+1,j-1)이 구간을 2씩 줄이므로 기저를 2개 처리한 것으로 볼 수 있다.

 

 

<코드>

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

int n, q, a[2001];
int dp[2001][2001];
int f(int i, int j) {
	int& ret = dp[i][j];
	if (ret != -1) return ret;

	if (i == j) return ret = 1;
	if (j - i == 1) return ret = (a[i] == a[j]);
	if (a[i] == a[j] && f(i + 1, j - 1) == 1) return ret = 1;
	return ret = 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	cin >> q;

	fill(&dp[0][0], &dp[2000][2001], -1);

	while (q--) {
		int s, e; cin >> s >> e;
		cout << f(s-1, e-1) << '\n';
	}
}