백준 10942_팰린드롬?(C++)

 

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

[문제 풀이]

DP를 이용하여 문제를 해결했습니다.  

이 문제의 경우 완전탐색으로 풀 경우 0.5초의 시간을 넘어가기 때문에 DP를 이용하였습니다.
세 가지의 경우로 나눠서 dp배열에 메모제이션 해주었습니다.

첫 번째 경우
문자열의 길이가 1인 경우 항상 팰린드롬은 성립하므로 dp[i][i] = 1로 메모제이션 해주었습니다.
두 번째 경우 
문자열의 길이가 2인 경우 앞뒤 문자가 같은지 판별하여 같은 경우 dp[i][i+1] = 1로 메모제이션 해주었습니다.
세 번째 경우
문자열의 길이가 3보다 큰 경우입니다. 이때는 시작지점의 문자열과 끝 지점의 문자열이 같으면서 dp[i + 1] [j - 1]이 같은 경우 부분 문자열의 길이가 팰린드롬이므로 dp[i][j] = 1로 메모제이션 해주었습니다.

그 후 M 번의 경우를 돌면서 dp배열의 값을 출력해주었습니다.

[코드]

#include<iostream>

using namespace std;

int N, M;
int arr[2001];
int dp[2001][2001] = { 0, };

int main() {

	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
		scanf("%d", &arr[i]);

	//길이가 1인 경우
	for (int i = 1; i <= N; i++)
		dp[i][i] = 1;

	//길이가 2인 경우
	for (int i = 0; i < N; i++) {
		if (arr[i] == arr[i + 1])
			dp[i][i + 1] = 1;
	}

	//길이가 3이상인 경우
	for (int k = 3; k <= N; k++) {
		for (int i = 1; i <= N - k + 1; i++) {
			int j = i + k - 1;

			if (arr[i] == arr[j] && dp[i + 1][j - 1])
				dp[i][j] = 1;
		}
	}

	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		int start, end;
		
		scanf("%d %d", &start, &end);
		printf("%d\n", dp[start][end]);

	}

    return 0;

}