팰린드롬?
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며,
S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며,
명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
1
2
3
4
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
S = 3, E = 3인 경우 1은 팰린드롬이다.
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다.
칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다.
팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
풀이
저번에 풀었던 팰린드롬 인코딩과 비슷하다.
이번에는 확인해야 하는 개수가 더 많은 것 같기는 하다.
2차원 배열을 만들고서, 각각 질문 쿼리에 대답할 수 있게 만들었다.
투 포인터라고 생각하고 풀었는데 dp에 가까운 것 같긴 하다.
방법은 짝수일때와 홀수일때 각각 가장 작은 범위부터 팰린드롬인지 확인한다.
맞으면 양쪽으로 늘려가며 확인하고 아니면 그 이상은 0으로 체크한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
int chk=0;
cin >> n;
vector<int> v(n+1);
int ans[2001][2001]={0};
for(int i=1;i<=n;i++){
cin >> v[i];
}
for(int i=1;i<=n;i++){
int l=i, r=i;
ans[l][r]=1;
chk = 1;
while(1){
l--;
r++;
if(l<=0 || r>n)break;
if(chk && v[l]==v[r])ans[l][r]=1;
else {
ans[l][r] = 0;
chk=0;
}
}
}
for(int i=1;i<n;i++){
int l=i, r=i+1;
if(v[l]==v[r]){
ans[l][r]=1;
chk = 1;
}
else{
ans[l][r]=0;
chk = 0;
}
while(1){
l--;
r++;
if(l<=0 || r>n)break;
if(chk && v[l]==v[r])ans[l][r]=1;
else {
ans[l][r] = 0;
chk=0;
}
}
}
cin >> t;
while(t-->0){
cin >> a >> b;
cout << ans[a][b] << '\n';
}
return 0;
}