[C/C++] 백준 10942번 - 팰린드롬? (DP)

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int dp[2001][2001];
int num[2001];
int N, M;
int s, e;

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

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
		dp[i][i] = 1; // 한자리수는 무조건 펠린드롬

		// "1 1", "2 2", "4 4"와 같이 두자리가 같은 경우들 기록
		if (i != 1 && num[i - 1] == num[i]) 
			dp[i - 1][i] = 1;
	}
		

	for (int i = 2; i <= N - 1; i++)
	{
		for (int j = 1; i + j <= N ; j++)
		{
			if (num[j] == num[i + j] && dp[j + 1][i + j - 1] == 1)
				dp[j][i + j] = 1;
		}
	}

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> s >> e;

		cout << dp[s][e] << '\n';
	}

}

 

풀이 방법

 

dp[s][e] : s~e구간 까지 팰린드롬 수인지 아닌지 "1" 또는 "0"으로 기록

 

1 2 3 2 1

1 2 2 1

 

팰린드롬 수를 판별하는 법은 간단하게 가운데로 이동하면서 양쪽 값을 비교해서 대칭이 된다면 팰린드롬 수 인 것을 알 수 있습니다. 그러나 문제에서 질문의 개수가 최대 1,000,000개 이므로 이러한 방법은 시간초과가 발생할 것입니다. 그렇기 때문에 dp배열로 메모제이션하면서 답을 구해야 합니다.

먼저, x에서 y구간의 수가 팰린드롬수인지 빠르게 알 수 있는 방법은 어떤 게 있을까요?

 

만약 x+1에서 y-1의 구간 수가 팰린드롬 수라면 x번째 수와 y번째수를 비교하는 것만으로도 x~y구간의 수가 팰린드롬 수인지 쉽게 판별할 수 있습니다. 

 

 

 

cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
		dp[i][i] = 1; // 한자리수는 무조건 펠린드롬

		// "1 1", "2 2", "4 4"와 같이 두자리가 같은 경우들 기록
		if (i != 1 && num[i - 1] == num[i]) 
			dp[i - 1][i] = 1;
	}

dp에 메모제이션 하는 작업을 하기 전에 "1", "3", "4"와 같은 한자리 수들은 무조건 팰린드롬 수이므로 dp[i][i]에 1을 기록해주고 그리고 "1 1", "3 3", "6 6"과 같은 두 자릿수도 팰린드롬 수이므로 dp[i-1][i]에 1을 기록해줍니다.

 

for (int i = 2; i <= N - 1; i++)
	{
		for (int j = 1; i + j <= N ; j++)
		{
			if (num[j] == num[i + j] && dp[j + 1][i + j - 1] == 1)
				dp[j][i + j] = 1;
		}
	}

i는 구간의 길이, 그리고 j는 구간이 시작하는 곳이라고 생각하시면 되겠습니다.

 

예를 들어 i가 4이고 j가 2라면 아래와 같은 경우입니다. 

dp[2][6]가 팰린드롬 수인지 확인하려면 어떻게 해야 할까요?

dp[3][5]값이 1인지(i가 2였을 때 기록된 값), 그리고 num[2]와 num[6]이 같은지를 따져보면 빠르게 구할 수 있게 됩니다.

 

 

 

www.acmicpc.net/problem/10942

10942번: 팰린드롬?