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

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

10942번: 팰린드롬?

 

dp문제입니다.

 

접근방식

 

1. 당연히 일반적인 방법으로 매번 검사하는건 불가능하다. 

O(n x m) => 2000 X  1,000,000 으로 가뿐히 10초를 넘기기 때문에

2. dp방식을 통해서 이미 검사해준 값이라면 또 탐색하지 말고 바로 값을 얻어오자

 

문제풀이 

 

1. top-down방식으로 dp[시작점][끝점]마다 가능한지 불가능한지 체크해주면서 넘어가자

2. 양 옆으로 한칸씩 줄이면서 탐색하는 구조 자세한 설명은 코드로

 

 

 

정답 코드

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

int n = 0, m = 0, st = 0, en = 0;
int arr[2000] = { 0, };
int dp[2000][2000];

int solved(int s, int e) {
	if (s >= e) return 1;
	if ((s + 1) == e) {
		if (arr[s] == arr[e])
			return 1;
		else
			return 0;
	}

	int& ret = dp[s][e];
	if (ret != -1) return ret;

	if (arr[s] == arr[e])
		ret = solved(s + 1, e - 1);
	else
		ret = 0;

	return ret;
}

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d", &arr[i]);
	
	for (int i = 0; i < 2000; i++)
		for(int j=0; j < 2000; j++)
			dp[i][j] = -1;

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &st,&en);
		printf("%d\n", solved(st - 1, en - 1));
	}


	return 0;
}