[알고리즘] C++ 백준 10942 팰린드롬?

백준 10942

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

10942번: 팰린드롬?

풀이 전 나의 생각

팰린드롬을 만들 수열에서 S번째 수부터 E번째 까지 수가 팰린드롬을 이루었다면 1, 아니라면 0을 반환한다.

 

그럼 우선 팰린드롬이 되기 위한 조건을 생각해봐야 한다.

 

백준 예제인 (1, 2, 1, 3, 1, 2, 1) 수열을 예시로 들어서 설명하면

 

팰린드롬의 길이가 1이라면 어떤 숫자든 팰린드롬이다. 왜냐하면 숫자 하나는 좌우반전을 해도 결국 같은 값이 나오기 때문이다. -> palindrom[i][i] = 1

 

그럼 다음으로 팰린드롬의 길이가 2면서 시작점과 끝점을 비교했을 때 값이 같은 경우는 모두 팰린드롬이다. (ex. 11, 22, 33) 

->

if (i != 1 && sequence[i] == sequence[i - 1])
{
palindrom[i - 1][i] = 1;
}

 

이제 여기까지는 별다른 조건없이 무조건 팰린드롬이 되는 경우다.

그럼 길이가 3이상 일때는 어떻게 팰린드롬을 확인하는지 알아야 한다.

이전의 길이가1, 2일 때 경우를 보면 결국 자신의 값들을 비교하면서 팰린드롬을 확인하고 있다.

 

그럼 3일 때도 자신의 값 즉, 시작점과 끝점을 확인하고 같다면 우선 팰린드롬의 조건은 하나 만족한다는 것이다.

예를 들어서 (1, 2, 1) 수열이 팰린드롬인지 확인하려고 하면 전에 말했듯이 시작점과 끝점을 우선 확인한다.

그 다음으로 바로 1과 1사이에 중간 값이 팰린드롬이지 아닌지 확인해줘야 할 것이다. 근데 중간의 값이 숫자 하나기 때문에 뭔가 감이 안잡힌다.

 

그럼 다음으로 길이가 4인 (1, 2, 2, 1) 수열이 팰린드롬인지 확인해보면 시작점(1), 끝점(1)이 같은 것을 확인했다.

다음으로 시작점과 끝점 사이에 있는 2, 2가 팰린드롬이 맞는지 확인해야 한다. 그럼 시작점 + 1, 끝점 - 1 을 확인하고 팰린드롬이 맞다면 수열(1, 2, 2, 1)은 팰린드롬이 되는 것이다.

 

그럼 이 공식을 이전에 구해놓았던 3일 때도 적용해 보면 (1, 2, 1)수열에 시작점 + 1, 끝점 - 1 즉, 시작점(2), 끝점(2)일 때 팰린드롬인지 확인하게 된다. 그럼 자연스럽게 중간의 값이 시작점, 끝점이 되고 처음에 구해놓았던 팰린드롬 초기값으로 인해 (1, 2, 1) 수열도 팰린드롬이 되는 것이다.

-> 

if (sequence[j] == sequence[i + j] && palindrom[j + 1][i + j - 1] == 1)
{
palindrom[j][i + j] = 1;
}

 

여기서 i는 구간이고 j는 시작점이다.

 

결론은 시작점인 j가 증가하며 구간 i만큼 탐색을 차례대로 진행하면 주어진 시작점과 끝점이 이전값을 비교하며

팰린드롬이 되는지 안되는지 모든 경우의 수를 구할 것이다. 이를 통해 문제에서 요구하는 답을 찾을 수 있다.

 

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int sequence[2001];
int palindrom[2001][2001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, t, start, end;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> sequence[i];
		palindrom[i][i] = 1;

		if (i != 1 && sequence[i] == sequence[i - 1])
		{
			palindrom[i - 1][i] = 1;
		}
	}

	for (int i = 2; i <= n - 1; i++)
	{
		for (int j = 1; i + j <= n; j++)
		{
			if (sequence[j] == sequence[i + j] && palindrom[j + 1][i + j - 1] == 1)
			{
				palindrom[j][i + j] = 1;
			}
		}
	}

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> start >> end;

		cout << palindrom[start][end] << '\n';
	}
}