BOJ 10942 | 팰린드롬?

처음에 떠올린 아이디어는 $[s, e]$ 구간이 들어오면 실시간으로 $[s, e]$ 구간이 팰린드롬이 맞는지 검사해서 출력하는 것이다.

$N=2000$ 정도면 재귀함수로도 무리 없이 돌아갈 거라고 생각해서 구현했더니 무난하게 AC 나왔다.

사실 $O(N^2)$으로 전처리 해서 쿼리를 $O(1)$로 수행하는 방식도 생각했는데 둘 중 뭐가 더 빠를까 해서 둘 다 제출해 본 결과 $N$이 작아서 그런지 큰 차이 없었다.

아마 좀 더 큰 $N$에서는 필요한 부분만 검사하는 처음 방식이 더 효율적이지 않을까 생각한다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int arr[2005];
int dp[2005][2005]; // 0:unknown 1:true 2:false
int N, M;

int palincheck(int l, int r){
	// len 0, len 1
	if (r-l == 0) return 1;
	if (r-l == 1){
		if (arr[l] == arr[r]) return dp[l][r] = 1;
		else return dp[l][r] = 2;
	}
	
	// not palindrome
	if (arr[l] != arr[r]) return dp[l][r] = 2;
	
	if (dp[l+1][r-1] == 0){ // unknown
		int rst = palincheck(l+1, r-1);
		if (rst == 1) return dp[l][r] = 1;
		else return dp[l][r] = 2;
	} else{ // known
		return dp[l][r] = dp[l+1][r-1];
	}
}

int main(){
	FASTIO;
	
	cin >> N; 
	for (int i = 1; i <= N; i++){
		cin >> arr[i];
		dp[i][i] = 1;
	}
	
	cin >> M;
	int l, r;
	for (int i = 0; i < M; i++){
		cin >> l >> r;
		palincheck(l, r);
		cout << (dp[l][r] == 1 ? 1 : 0) << endl;
	}
	
}