[백준 C++] 10942번: 팰린드림?

1. 문제

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

10942번: 팰린드롬?

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> v;
int dp[2003][2003];

// 팰린드롬인지 확인하는 알고리즘
bool is_palindrome(int start, int end) {

	// 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문자열이 팰린드롬일 경우, True
	if (v[start] == v[end] && (end - start == 1 || dp[start + 1][end - 1]))
		return true;

	return false;
}

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

	int N, M, S, E;

	// 수열의 크기(N) 입력
	cin >> N;

	// 수열 입력
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}

	// TestCase
	/*
	*		1	2	1	3	1	2	1
	*	1	o	x	o	x	x	x	o
	*	2		o	x	x	x	o	x
	*	3			o	x	o	x	x
	*	4				o	x	x	x
	*	5					o	x	o
	*	6						o	x
	*	7							o
	*/
	// DP 알고리즘
	// dp[start][end] = start번째 ~ end번째 문자까지 문자열이 팰린드롬인지 True/False
	for (int len = 0; len < N; len++) {
		for (int start = 0; start + len < N; start++) {
			if (len == 0)	// 문자열 길이가 1이면, 무조건 팰린드롬
				dp[start][start + len] = 1;
			else if (is_palindrome(start, start + len))	// 팰린드롬인지 확인
				dp[start][start + len] = 1;
		}
	}

	// 질문의 개수(M) 입력
	cin >> M;

	// 수열의 시작점(S)와 끝점(E)가 입력되면 계산된 dp[S - 1][E - 1] 값을 출력
	for (int i = 0; i < M; i++)
	{
		cin >> S >> E;
		cout << dp[S - 1][E - 1] << "\n";
	}

	return 0;
}