[Baekjoon] 10942번 팰린드롬?.cpp

[백준] 10942번 팰린드롬? 문제 링크

DP 문제로, 수열 내 원소들이 좌우대칭을 이룰 때 팰린드롬이라고 한다.

pal이라는 2차원 배열을 만들어 pal[s][l]의 값은 's번째 숫자부터 l길이의 부분수열이 팰린드롬 수열인가?'를 저장한다.

기본적으로 하나의 숫자는 반드시 팰린드롬이고, 두 개의 연속된 숫자가 같은지 판단하여 길이 1과 2에 해당하는 팰린드롬 여부를 먼저 구해주었다.

그리고 그 이상의 길이를 가지는 수열은 이미 구해놓은 팰린드롬 수열의 시작점이 s이고 끝점이 e일 때 s-1과 e+1의 문자가 서로 같다면 s-1 ~ e+1의 수열도 팰린드롬 수열이 된다. 이러한 방식이 동적할당법 즉, DP를 활용하는 방법이 된다.

이를 미리 구해놓은 길이 1과 2의 부분 수열들에 적용하여 특정 지점에서 시작하는 모든 길이의 팰린드롬 수열을 구해주었다.

아래는 위 아이디어를 적용한 코드 전문이다.

#include <iostream>

int n, m;

int arr[2001] = { 0, };

bool pal[2001][2001] = { 0, };

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n;

	for (int count = 1; count <= n; count++) {
		std::cin >> arr[count];
		pal[count][1] = true;

		if (arr[count] == arr[count - 1]) {
			pal[count - 1][2] = true;
		}
	}

	for (int start = 1; start < n; start++) {
		int stmp = start - 1;
		int etmp = start + 1;

		for (int etmp = start + 1; stmp >= 1 && etmp <= n; stmp--, etmp++) {
			if (arr[stmp] == arr[etmp] && pal[stmp + 1][etmp - stmp - 1]) {
				pal[stmp][etmp - stmp + 1] = true;
			}
			else {
				break;
			}
		}

		stmp = start - 1;
		for (int etmp2 = start + 2; stmp >= 1 && etmp2 <= n; stmp--, etmp2++) {
			if (arr[stmp] == arr[etmp] && pal[stmp + 1][etmp - stmp - 1]) {
				pal[stmp][etmp - stmp + 1] = true;
			}
			else {
				break;
			}
		}
	}

	std::cin >> m;

	int s, e;
	for (int count = 0; count < m; count++) {
		std::cin >> s >> e;

		std::cout << pal[s][e - s + 1] << "\n";
	}
}