[BOJ-10942] 팰린드롬?(C++)

백준 10942 - 팰린드롬?

 

 

10942번: 팰린드롬?

 

 

문제 설명

 

 - 명우와 홍준이는 팰린드롬 놀이를 한다.

 

 - 홍준이가 N개의 자연수를 제시한다.

 

 - 홍준이는 명우에게 M번의 질문을 한다.

 

 - 각 질문에는 홍준이가 제시한 N개의 자연수의 시작 번호S와 끝 번호 E가 주어진다.

 

 - S에서 E까지의 숫자가 팰린드롬을 만드는지 출력하라.

 

 - 해당 질문이 팰린드롬이라면 1을, 아니라면 0을 출력하라.

 

---

 

입력 값

 

 - 첫째 줄에 수열의 크기 N( 1<= N <= 2,000)

 

 - 둘째 줄에는 홍준이가 적은 N개의 숫자가 순서대로 주어진다.

   적은 수는 100,000보다 작거나 같은 자연수이다.

 

 - 셋째 줄에는 홍준이가 한 질문의 개수 M ( 1<= M <= 1,000,000)이 주어진다.

 

 - 넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하니씩 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 수열의 최대 크기는 2000이다. 

 

 - 총 질문의 최대 개수는 100만개이다.

 

 - S와 E가 주어졌을 때 팰린드롬인지 판단하는 방법은, 양 끝을 비교하여 같은지 확인하는 것이다.

   즉, 길이가 L일때 팰린드롬인지 판단하는 시간복잡도는 O(L/2)이다.

 

 - 즉, 질문당 팰린드롬인지 판단하게 된다면 최대 100만X1000 = 10억이 되기 때문에 불가능하다.

 

 - 질문 수열이 팰린드롬인지 판단하는 과정에서 반복되는 경우가 발생할 수 있다.

   S=1, E=5인 경우 팰린드롬이라고 한다면, S=2, E=4일때도 팰린드롬이 되고, S=3, E=3일때도 팰린드롬이 된다.

   즉, S=1, E=5를 받고, 다음에 S=2, E=4를 받는 다면 다시 계산하지 않고, 팰린드롬임을 알 수 있다.

 

 - 결론적으로 메모이제이션을 이용하여 반복 작업을 하지 않도록 하면, 시간을 줄일 수 있다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int arr[2001];
int palindrome[2001][2001];

int findPalindrome(int n1, int n2) {

	if (n1 > n2) {
		return 1;
	}


	if (palindrome[n1][n2] != 0) {
		return palindrome[n1][n2];
	}

	if (arr[n1] == arr[n2]) {
		palindrome[n1][n2] = findPalindrome(n1 + 1, n2 - 1);
	}
	else {
		palindrome[n1][n2] = -1;
	}


	return palindrome[n1][n2];


}

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

	int N,M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		arr[i] = n;
	}

	cin >> M;

	for (int i = 0; i < M; i++) {
		int a, b ;
		cin >> a >> b;
		
		int now = findPalindrome(a-1, b-1);
		if (now == -1) {
			cout << 0 << "\n";
		}
		else {
			cout << 1 << "\n";
		}
	}
	

	return 0;
}