알고리즘 스터디

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

10942번: 팰린드롬?

백준 10942 팰린드롬

처음에 팰린드롬이 뭐지? 해서 검색해봤더니 앞에서 읽으나 뒤에서 읽으나 똑같은 단어라고 한다.

그냥 풀어도 풀수는 있지만 DP에 있는 문제여서 어떤 부분을 메모라이즈 해야되나 생각했는데

전단계 결과에 제일 처음숫자와 제일 마지막 숫자만 비교하면 될 것 같았다.

다만 고른 숫자의 개수가 1개나 2개인경우는 직접 계산하고 나머지는 메모라이즈 하도록 구현했다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>
#define ll long long

using namespace std;

int n, m, s, e;
vector<int> a(2001, 0);
vector<vector<bool>> dp(2001, vector<bool>(2001));

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	// 길이가 1인부분은 모두 true
	for (int i = 1; i <= n; ++i) {
		dp[i][i] = true;
	}

	// 길이가 2인부분은 직접 계산해서 true/false
	for (int i = 1; i <= n - 1; ++i) {
		if (a[i] == a[i + 1]) dp[i][i + 1] = true;
	}

	for (int i = n - 1; i >= 1; --i) {
		for (int j = i + 2; j <= n; ++j) {
			if (a[i] == a[j] && dp[i + 1][j - 1]) {
				dp[i][j] = true;
			}
		}
	}
	
	cin >> m;

	for (int i = 0; i < m; ++i) {
		cin >> s >> e;
		cout << dp[s][e] << '\n';
	}

	return 0;
}