백준 BOJ 10942 - 팰린드롬?

DP문제

 

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

10942번: 팰린드롬?

dp[i][j]를 i번째 수부터 j번째 수까지 붙여 만든 문자열이 팰린드롬인가? (1 or 0) 으로

정의해주면 된다

일단 i와 j가 같은 경우에는 항상 팰린드롬일 것이고, 길이가 짝수인 팰린드롬은 i+1 와 j 번째 숫자가 같아야 한다.

이것들을 먼저 처리해 큐에 넣어주고

BFS를 통해 순회해주며 DP배열을 채우면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[2345][2345] = {0}; // i부터 j까지 수가 팰린드롬인가? T/F 
int arr[2345] = {0};

queue<pair<int,int>> q;

int main(){
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	for(int i=0; i<n; i++) cin >> arr[i];
	for(int i=0; i<2345; i++){
		dp[i][i] = 1;
		q.push({i,i});
	}
	for(int i=1; i<n; i++) if(arr[i-1] == arr[i]){
		dp[i-1][i] = 1;
		q.push({i-1,i});
	}
	
	while(!q.empty()){
		auto p = q.front(); q.pop();
		int s = p.first;
		int e = p.second;
		
		if(s>e) continue;
		
		if(0<=s-1 && e+1<n && arr[s-1] == arr[e+1]){
			dp[s-1][e+1] = 1;
			q.push({s-1,e+1});
		}
	}
	
	int m,s,e;
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> s >> e;
		cout << dp[s-1][e-1] << "\n";
	}
	return 0;
}