<Baekjoon> #10942 Dynamic Programming_Palindrome c++

#10942 팰린드롬

• Palindrome
  회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.
  (참고: 위키피디아)

이 문제는 여러가지 방법으로 풀 수 있겠지만 시간 제한과 메모리 제한 때문에 dp로 풀어야 한다.dp로 풀지 않고는 s와 e를 양 끝에서부터 탐색하면서 찾을 수도 있다.

1. bool dp[i][j]에서 i에서 j까지 팰린드롬이 맞으면 true, 아니면 false를 저장한다.

• dp[i][j]에서 i==j인 경우는 반드시 true

	for (int i = 1; i <= n; i++)
		dp[i][i] = true;

• dp[i][j]에서 j==i+1인 경우도 반드시 true

	for (int i = 1; i < n; i++)
		if (num[i] == num[i + 1])
			dp[i][i + 1] = true;

2. s~e가 팰린드롬일 경우 num[s]==num[e]이고 s+1 ~ e-1도 팰린드롬이라는 점을 이용한다.

	for (int i = 2; i < n; i++) {
		for (int j = 1; j<=n-i; j++) {
			int k = i + j;
			if (num[j] == num[k] && dp[j + 1][k - 1])
				dp[j][k] = true;
		}
	}

시작 위치 j에서 i만큼 떨어진 위치를 끝나는 위치라 두고 비교한다.
위에서 이미 길이가 1,2인 경우는 구했으니 시작위치에서 2만큼 떨어진, 즉 총 길이가 3일 때부터 팰린드롬인지 검사한다.

3. 참고로 시간 제한 때문에 cin,cout 대신 scanf_s, printf 를 사용해야 한다

전체 코드

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

using namespace std;
const int MAX = 2001;
bool dp[MAX][MAX];
int n;
vector<int>num;
void palindrome() {
	for (int i = 1; i <= n; i++)
		dp[i][i] = true;
	for (int i = 1; i < n; i++)
		if (num[i] == num[i + 1])
			dp[i][i + 1] = true;
	for (int i = 2; i < n; i++) {
		for (int j = 1; j<=n-i; j++) {
			int k = i + j;
			if (num[j] == num[k] && dp[j + 1][k - 1])
				dp[j][k] = true;
		}
	}
}
int main() {
	memset(dp, false, sizeof(dp));
	scanf_s("%d", &n);
	num = vector<int>(n+1);
	for (int i = 1; i <= n; i++)
		scanf_s("%d", &num[i]);
	palindrome();
	int m;
	scanf_s("%d", &m);
	for (int i = 0; i < m; i++) {
		int s, e;
		scanf_s("%d %d", &s, &e);
		printf("%d\n", dp[s][e]);
	}
	return 0;
}