( "팰린드롬 "이란 뒤집어도 똑같은 수를 의미한다. )
일단 시간 제한이 0.5초(5천만줄) 정도이고, 입력의 크기가 2000 개의 수열의 크기, 백만개의 질문의 개수이다. 이를 보아 질문마다 2000 번의 연산을 하게 된다면 문제가 바로 터진다는 걸 알 수 있다.
때문에 백만개의 질문마다 log(n) 의 연산을 하던가 아예 처음에 다 계산한 이후 O(1) 의 복잡도로 답을 내버리던가 해야 한다.
팰린드롬은 대표적인 dp 문제라고 할 수 있다. 예를 들어
1, 2, 1, 3, 1, 2, 1
위와 같이 7개의 수가 있을 때 (3, 7) 이 팰린드롬인지 확인해보자.
(3,7) 은 1, 3, 1, 2, 1 로 양끝의 수가 같은 팰린드롬 같은(?) 수이다. 이 때 양끝의 수가 같으니 (3, 7) = (4, 6) 이라는 걸 유추할 수 있다. 이 상태 관계를 가지고 Dynamic Programming 을 해줄 수 있다.
즉, (a,b) 는 a번째 수와 b 번째 수가 같다면 (a,b) = (a+1, b-1) 이 되고, 당연히 같지 않다면 (a,b) = 0 이 된다.
#include <iostream>
using namespace std;
int arr[2001];
int dp[2001][2001];
void initialize() {
for (int i = 0; i < n; i++) {
for (int j =1; j <= n - i; j++) {
if (i == 0) {
dp[j][j + i] = 1;
}
else if (i == 1) {
dp[j][j + i] = (arr[j] == arr[j + i]) ? 1 : 0;
}
else {
if (arr[j] == arr[j + i])
dp[j][j + i] = dp[j + 1][j + i - 1];
else
dp[j][j + i] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, a, b;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
// initialize dp arr
initialize();
cin >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b;
cout << dp[a][b] << "\n";
}
return 0;
}
