[BAEKJOON 10942번] (C++) 팰린드롬?

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

칠판에 적혀 있는 숫자들을 arr 에 저장하고 2차원 배열 dp 를 통해 ( dp[s][e]  ( 질문이 S E 일 때의 결과) ) 결과들을 저장하여 이미 계산이 이뤄진 경우의 수를 반복 계산하지 않도록 한다.

펠린드롬을 검사할 때에는 첫번째 index와 마지막 index부터 하나씩 더하고, 빼면서 비교하여 체크한다.

 

코드

#include <iostream>
#include <string.h>

using namespace std;

int N;
int arr[2001];
int M;

int dp[2001][2001];

bool sol(int s, int e) {

	//이미 확인한 경우
	if (dp[s][e] != -1)
		return dp[s][e];

	//펠린드롬인지 검사
	bool answer = 1;
	for (int i = 0; i <= (e - s) / 2; i++)
	{
		if (arr[s + i-1] != arr[e - i-1]) {
			dp[s][e] = 0;
			answer = 0;
			break;
		}
	}
	dp[s][e] = answer;
	return answer;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 2001; i++) 
		memset(dp[i], -1, sizeof(int) * 2001);

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

	bool ans[1000000];

	int S, E;
	for (int i = 0; i < M; i++)
	{
		cin >> S >> E;
		ans[i] = sol(S, E);
	}

	for (int i = 0; i < M; i++)
	{
		cout<<ans[i]<<"\n";
	}

	return 0;
}

결과