[C++] 백준 10942 팰린드롬?

#include <iostream>
 
int arr[2001] = {};
bool dp[2001][2001] = {};
 
int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int N = 0;
	std::cin >> N;
 
	for (int i = 1; i <= N; ++i)
	{
		std::cin >> arr[i];
	}
 
	for (int i = 1; i <= N; ++i)
	{
		if (arr[i] == arr[i + 1])
		{
			dp[i][i + 1] = true;
		}
	}
 
	for (int i = 1; i <= N; ++i) 
	{
		dp[i][i] = true;
	}
 
 
	for (int i = N - 1; i >= 1; --i)
	{
		for (int j = i + 2; j <= N; ++j) 
		{
			if (arr[i] == arr[j] && dp[i + 1][j - 1])
			{
				dp[i][j] = true;
			}
		}
	}
 
	int M = 0;
	std::cin >> M;
 
	int start = 0;
	int end = 0;
 
	for (int i = 0; i < M; ++i)
	{
		std::cin >> start >> end;
		std::cout << dp[start][end] << "\n";
	}
 
	return 0;
}

 

dp[i][j]은 i열에서 j열까지의 팰린드롬입니다.

바로 옆이라면 2개라도 팰린드롬이 되기 때문에 i, i+1이 똑같을 경우 그 옆도 true로 해줍니다.

이후 본인만 나와도 true이기 때문에 다 i, i는 true로 했습니다.

이후부터는 [i+1][j-1] 두개가 똑같고 그 전까지 모두 다 팰린드롬이 된다고 한다면 dp[i][j]도 됩니다.

그렇게 쭉 계산합니다.