[백준 C++] 10942 팰린드롬? - 다이나믹프로그래밍

10942번: 팰린드롬?

#include <iostream>
using namespace std;

int Num[2000];
bool DP[2000][2000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> Num[i];
	}

	for (int i = 0; i < N; ++i)
	{
		DP[i][i] = true;

		if (i < N - 1)
		{
			DP[i][i + 1] = (Num[i] == Num[i + 1]);
		}
	}

	for (int i = N - 3; i >= 0; --i)
	{
		for (int j = i + 2; j < N; ++j)
		{
			DP[i][j] = (Num[i] == Num[j] && DP[i + 1][j - 1]);
		}
	}

	int M;
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int S, E;
		cin >> S >> E;
		cout << DP[S - 1][E - 1] << '\n';
	}
}

---

 

행, 열이 각각 시작지점, 끝지점을 뜻하는 2차원 DP 배열에 팰린드롬 여부를 저장해서 푸는 문제입니다.

팰린드롬인 경우를 다음과 같이 일반화할 수 있습니다.

 

1. 시작지점과 끝지점이 같은 경우 - 길이가 1인 팰린드롬

2. 길이가 2일 때, 각 지점에 해당하는 두 수가 같은 경우

3. 길이가 3이상일 때, 시작지점과 끝지점의 두 수가 같고 두 지점 사이(시작지점+1~끝지점-1)의 수열이 팰린드롬일 경우

 

3번 경우, 점화식을 다음과 같이 표현할 수 있습니다.

DP[i][j] = (Num[i] == Num[j] && DP[i + 1][j - 1])

 

 

위에서 정의한 일반화 과정을 통해서 예제의 DP 배열을 모두 채우면 배열의 값이 위의 그림처럼 표현됩니다.