C++ / 백준 / 10942 / 팰린드롬?

문제

 

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

 

 

문제풀이

 

팰린드롬이란 역순으로 읽어도 같은 말이 되는 말을 의미한다.

앞 뒤를 바꿔서 기존과 같은 수열이면 YES를 출력하면 되는 문제이다.

 

팰린드롬이 되는 시작 인덱스와 끝 인덱스를 2차원 벡터로 표현하였다.

ex) 1부터 3자리까지 팰린드롬이면 vector[1][3]=true, 거짓이면 vector[1][3]=false

 

시작 인덱스가 팰린드롬의 중간 인덱스로 두고 문제를 풀었다.

그리고 팰린드롬 수의 길이를 홀수, 짝수의 경우로 나눴다.

홀수인 경우, 시작 지점 앞뒤로 수가 있고 앞뒤 숫자가 같으면 vector[start-idx][start+idx]=true가 된다.

idx는 1부터 팰린드롬 수의 끝까지 증가한다, 중간에 팰린드롬 수가 아니면 다음 시작 인덱스로 넘어간다.

 

짝수인 경우, 먼저 시작 인덱스의 수와 바로 옆 한 칸(왼쪽 또는 오른쪽 방향 하나)과 같은지를 확인해야 한다.

같다면 두 수를 기준으로 양옆 한 칸씩 범위를 넓혀가며 숫자가 같은지를 확인하면 된다.

 

while문을 이용해 1부터 N까지의 범위를 넘어가는지, 양 끝 인덱스의 숫자가 같은지를 판별하였다.

 

코드

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

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

	int N(0), M(0);
	cin >> N;
	vector<int>seq(N + 1, 0);
	for (int idx = 1; idx <= N; ++idx)	cin >> seq[idx];
	cin >> M;

	vector<vector<bool>>isPalindrome(N + 1, vector<bool>(N + 1, false));

	for (int start = 1; start <= N; ++start) {
		int idx = 1;
		isPalindrome[start][start] = true;
		while (1 <= start - idx && start + idx <= N && seq[start - idx] == seq[start + idx]) {
			isPalindrome[start - idx][start + idx] = true;
			++idx;
		}
		if (start + 1 > N || seq[start] != seq[start + 1]) continue;
		isPalindrome[start][start + 1] = true;

		idx = 1;
		while (1 <= start - idx && start + idx + 1 <= N && seq[start - idx] == seq[start + idx + 1]) {
			isPalindrome[start - idx][start + idx + 1] = true;
			++idx;
		}
	}

	int start(0), end(0);
	for (int idx = 0; idx < M; ++idx) {
		cin >> start >> end;
		cout << isPalindrome[start][end] << '\n';
	}
}