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

이 문제는 다이나믹 프로그래밍으로 풀었다.

 

문제의 시간 제한이 0.5초이므로 약 5,000만번의 연산 이하로 알고리즘을 짜야 한다.

 

수열의 크기 N이 최대 2,000이므로 2,000 * 2,000 의 배열을 만들 수 있고, 400만 정도의 연산으로 dp배열을 모두 채울 수 있다. 따라서 다이나믹 프로그래밍으로 문제를 해결할 수 있다.

 

dp[i][j] : 구간 [i, j] 의 팰린드롬 여부 저장

으로 정했고, 구간의 길이에 따라 연산을 다르게 하였다.

 

구간의 길이가 1인 경우, 즉 start와 end가 같을 경우에는 당연히 팰린드롬이므로 true를 저장한다.

구간의 길이가 2인 경우에는 두 숫자가 서로 같을 경우 true를 저장한다.

구간의 길이가 3 이상인 경우에는, start = i + 1, end = j - 1로 안쪽의 dp가 true이고, 양 끝이 숫자가 같을 경우에 true를 저장하여 문제를 해결할 수 있었다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 2000

int N, M;
int arr[MAX + 1];
bool dp[MAX + 1][MAX + 1];

bool inRange(int x) {
	if (1 <= x && x <= N) {
		return true;
	}
	return false;
}

void solve() {

	for (int dist = 1; dist <= N; dist++) {
		for (int i = 1; i <= N; i++) {
			int start = i;
			int end = start + dist - 1;

			if (inRange(end)) {
				if (dist == 1) {
					dp[start][end] = true;
				} else if (dist == 2) {
					if (arr[start] == arr[end]) {
						dp[start][end] = true;
					}
				} else {
					int innerStart = start + 1;
					int innerEnd = end - 1;
					
					if (dp[innerStart][innerEnd] && arr[start] == arr[end]) {
						dp[start][end] = true;
					}
				}
			}
		}
	}
}

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

	solve();

	cin >> M;
	for (int i = 0; i < M; i++) {
		int S, E;
		cin >> S >> E;

		if (dp[S][E]) {
			cout << 1 << '\n';
		} else {
			cout << 0 << '\n';
		}
	}
}

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

	input();

	return 0;
}