BOJ 팰린드롬?

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

정수형 배열을 입력받고 구간의 값이 팰린드롬인지 판단하는 문제다.

처음에는 문자열로 접근해서 reverse를 사용했지만 2000번에 대해서 1백만 번씩 뒤집히니 시간 초과.

결국 dp로 풀었다.

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

int f(vector<vector<int>>& d, vector<int>& ar, int s, int e) {
	if (s >= e) return 1;
	if (d[s][e] != -1) return d[s][e];
	if (ar[s] == ar[e]) d[s][e] = f(d, ar, s + 1, e - 1);
	else d[s][e] = 0;
	return d[s][e];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m, x, y;
	cin >> n;
	vector<vector<int>> d(n + 1, vector<int>(n + 1, -1));
	vector<int> ar(n + 1);

	for (int i = 1; i <= n; i++) cin >> ar[i];
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		cout << f(d, ar, x, y) << '\n';
	}
	return 0;
}

탑다운 dp로 풀었는데 각 구간에 대해서 대칭되는 범위의 숫자가 같다면 범위를 좁혀서 재고 다르다면 0을 저장해준다.