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

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

 

메모이제이션 기법을 이용해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

vector<int> v;
vector<vector<int>> cache;

int DP(int start, int end) {

	int& ret = cache[start][end];

	if (start >= end)
		return ret = 1;

	if (cache[start][end] != -1)
		return ret;

	if (v[start] != v[end])
		return ret = 0;

	return ret = DP(start + 1, end - 1);
}

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

	cin >> n;
	v = vector<int>(n + 1);
	cache = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		cout << DP(start, end) << "\n";
	}
}