[10942] 팰린드롬?

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

10942번: 팰린드롬?

 

접근:

• 팰린드롬을 확인하는 함수인 isFel(int i, int j)는 주어진 수열의 i번째, j번째가 같은 지 확인하고, 같으면 다음 단계인 isFel(i+1,j-1)을 확인한다.
• cache배열은 2000*2000 2차원 배열을 사용했다. 이미 답이 나왔던 팰린드롬이 sub problem으로 나온다면 cache를 사용하여 바로 답을 반환한다.
• 시간복잡도는 O(M*N)이지만, 하나의 함수 호출 시 팰린드롬을 검사하는 최대 횟수는 1000회이며, cache를 사용하기 때문에 O(M*N)이 그대로 가지는 않을 것 같다.

 

코드:

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

vector<int> A;
int N, M;
int cache[2000][2000];

// line의 i부터 j까지가 펠린드롬인지 확인
bool isFel(int i, int j)
{
	if (i == j) return true;
	if (i == j - 1) return A[i] == A[j];
	
	int& ret = cache[i][j];
	if (ret != -1) { return ret; }

	return ret = (A[i] == A[j] && isFel(i + 1, j - 1));
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	memset(cache, -1, sizeof(cache));
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		A.push_back(a);
	}

	cin >> M;
	while (M--)
	{
		int i, j;
		cin >> i >> j;
		cout << isFel(i - 1, j - 1) << "\n";
	}
	return 0;
}