백준 - 19042 팰린드롬

 

해결과정 - DP

첫번째 방법 무식하게 푸는 방법은 모두가 생각한듯이 S, E가 주어졌을때 {S, E} {S - 1, E - 1} 이런식으로 비교를 해가며 푸는 방식이다 하지만 질문 M이 많을경우 약 n^2 * m의 시간복잡도가 발생하게 된다

 

두번째 방식은 S와 E의 값이 같을때 S와 E의 안쪽이 팰린드롬이면 S 와 E도 팰린드롬이라는 것에서 미리 팰린드롬 보드를 제작할수 있다 1일때는 팰린드롬임이 분명하고 2일때부터 위의 발상을 적용할 수 있다 위를 표현하면

if(S == E) 일때 board[Length][Start] = board[Length - 2][Start + 1] 이라는 공식이 나오게 된다

계산의 편리성을 위해 board는 1부터 시작하도록 구성하였다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<deque>
#include<unordered_set>
#include<unordered_map>
#include<cmath>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

int board[2001][2001];

int main() {
	Fast;
	
	int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++)
			board[i][j] = 1;
	}

	//보드를 초기화 한다
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= n - i + 1; j++) {
			if(arr[j - 1] == arr[j + i - 2])
				board[i][j] = board[i - 2][j + 1];
			else
				board[i][j] = 0;
		}
	}

	int m;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int S, E;
		cin >> S >> E;

		int diff = E - S + 1;

		cout << board[diff][S] << '\n';
	}
	return 0;
	
}

 

후기

골드문제는 아닌듯하다