문제 간략 설명

홍준이가 자연수 N개를 칠판에 적는다. 그 다음 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째까지의 수가 팰린드롬을 이루는지를 물어본다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

풀이 방법

  1. DP로 풀겠습니다.
  2. 길이가 1이면 true
  3. 길이가 2이면 두 문자가 같으면 true
  4. 길이가 3 이상이면 왼쪽 오른쪽 끝이 같고 가운데 부분은 이전에 풀었던 DP에서 가져와서 전부 true면 true

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int S, E;

vector<int> vec;

bool dp[2001][2001];

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	vec.resize(N);

	for (int i = 0; i < N; i++)
		cin >> vec[i];
	
	for (int i = 0; i < N; i++)
		dp[i][i] = true;

	for (int i = 0; i < N - 1; i++)
		if (vec[i] == vec[i + 1])
			dp[i][i + 1] = true;

	for (int len = 3; len <= N; len++) {
		for (int i = 0; i + len <= N; i++) {
			int j = i + len - 1;
			if (vec[i] == vec[j] && dp[i + 1][j - 1])
				dp[i][j] = true;
		}
	}

	cin >> M;

	while (M--) {
		cin >> S >> E;

		cout << dp[S - 1][E - 1] << '\\n';
	}

	return 0;
}

Key Points