[BOJ10942] 팰린드롬

[BOJ10942] 팰린드롬

문제 링크

생각의 흐름

• 기본적인 팰린드롬의 아이디어에 대해 먼저 생각해보았다.
• 주어진 문자열의 시작점과 끝점에 대해 시작점은 오른쪽으로 한칸, 끝점은 왼쪽점으로 한칸 이동하며 둘의 문자가 같은지에 대한 여부를 확인하며 진행하면 된다.
• 이 문제의 경우, 명령어 수가 1000000개가 나오고 최악의 경우를 생각한다면, 1000000 * 2000(문자열의 길이) = 2,000,000,000 의 연산 횟수가 되어 시간 초과가 난다.
• 즉, 전처리 작업 을 통하여 명령어에 대한 반복적인 쿼리작업을 빠른 시간안에 해야한다.
• 전처리 작업에 대한 구현에 있어서는 DP를 생각했다.
• DP[i][j]를 i~j까지의 문자열이 팰린드롬인지에 대한 여부를 true, false로 저장하는 bool타입 2차원 배열 로 선언하였다.
• DP[i][j]는 DP[i+1][j-1]이 true인 상황(i+1번째~ j-1 번째 문자열이 팰린드롬) 에서, i번째 문자와 j번째 문자가 같다면 이 역시도 팰린드롬이 된다.
• 이렇게 DP 배열을 만들어두면, 쿼리작업에 대해 O(1) 로 팰린드롬인지 아닌지에 대해 찾을 수 있게 된다.

#include <iostream>
using namespace std;

bool dp[2005][2005];
int arr[2005];
int N, M;

void palind() {
	for (int i = N; i >= 1; i--) {
		for (int j = i; j <= N; j++) {
			if (i == j) { //문자열의 길이가 1일때는 항상 팰린드롬
				dp[i][j] = true;
			}
			else if (i + 1 == j) { //문자열의 길이가 2일때는 두 문자의 일치여부 비교
				dp[i][j] = (arr[i] == arr[j] ? true : false);
			}
			else {
				if (!dp[i + 1][j - 1]) { //i+1 ~ j-1번째 문자열이 팰린드롬이 아닌 경우
					dp[i][j] = false;
				}
				else { //i+1 ~ j-1번째 문자열이 팰린드롬인 경우
					dp[i][j] = (arr[i] == arr[j] ? true : false);
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	palind();
	cin >> M;
	while (M--) {
		int a, b;
		cin >> a >> b;
		cout << dp[a][b] << '\n';
	}
	return 0;
}