BOJ_10942 [ 팰린드롬? ]

문제

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

10942번: 팰린드롬?

문제 해결 방법

효율적으로 풀기 위해서는 DP 알고리즘 사용해야 된다.

2차원 배열 변수 DP를 선언 후 Bottom - up 방식으로 문제를 해결하면 된다.

시작과 끝에 해당되는 인덱스에 값이 같으면 안에가 팰린드롬인지 아닌지만 알고 있으면 된다.

if( arr[시작] 과 arr[끝]이 같고  dp[시작+1][끝-1]이 팰린드롬이라면)

       DP[시작][끝] = 팰린드롬이다.

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/Dynamic%20programming/BOJ_10942.cpp

jokerKwu/BOJ_Algorithm

#include<iostream>
#include<vector>
using namespace std;
#define MAX 2002
bool dp[MAX][MAX];
int arr[MAX];
int N, M;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= N; i++) dp[i][i] = true;
	for (int i = 1; i < N; i++)
		if (arr[i] == arr[i + 1]) dp[i][i + 1] = dp[i + 1][i] = true;
	
	for (int i = 2; i < N; i++) {	//이게 길이
		for (int j = 1; j <= N-i; j++) {
			if (arr[j] == arr[j + i] && dp[j + 1][j + i - 1])
				dp[j][j + i] = dp[j + i][j] = true;
		}
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		int s, e,answer = 0;
		cin >> s >> e;
		if (dp[s][e]) answer = 1;
		cout << answer << '\n';
	}

	return 0;
}