백준 10942번: 팰린드롬?

[문제 링크]

10942번: 팰린드롬?

---

팰린드롬인 경우는 다음과 같다.

if(S == E) 일 경우 길이가 1이므로 무조건 팰린드롬,

else if(S+1 == E && arr[S] == arr[E]) 일 경우 길이가 2며 양쪽 끝이 서로 같으므로 팰린드롬,

else if(arr[start] == arr[end] && memo[start+1][end-1] == 1) 일 경우 즉, 양쪽 끝의 숫자가 같고, 양쪽 숫자를 제외한 나머지 부분이 팰린드롬일 경우 팰린드롬이다.

---

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

int arr[2001], memo[2001][2001];

int Topdown(int start, int end)
{
	if (start == end) return 1;
	if (start + 1 == end) return arr[start] == arr[end] ? 1 : 0;

	int& ret = memo[start][end];
	if (ret != -1) return ret;

	if (arr[start] == arr[end] && Topdown(start + 1, end - 1))
		return ret = 1;
	else
		return ret = 0;
}

void Bottomup(int N)
{
	for (int i = 1; i <= N; i++)
		memo[i][i] = 1;

	for(int end = 1; end<=N; end++)
		for (int start = 1; start < end; start++)
		{
			if (start + 1 == end)
				memo[start][end] = arr[start] == arr[end] ? 1 : 0;
			else if (arr[start] == arr[end] && memo[start + 1][end - 1])
				memo[start][end] = 1;
			else
				memo[start][end] = 0;
		}
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	Bottomup(N); // 모든 경우에서 팰린드롬 여부를 미리 계산

	int M;
	cin >> M;
	while (M--)
	{
		int S, E;
		cin >> S >> E;
		cout << Topdown(S, E) << '\n';
		
		cout << memo[S][E] << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 95 day