문제
풀이
팰린드롬 : 왼쪽에서 읽었을 때랑, 오른쪽에서 읽었을 때랑 똑같은 숫자 배열을 의미한다. 단순하게 맨끝에서부터 중간까지 일일이 비교하며 팰린드롬이 true인지 false인지 판단하는 것은 시간초과가 일어난다. 그래서 다이나믹 프로그래밍을 사용하는데, dp[i][j] = i~j까지 팰린드롬인가(=1), 아닌가(=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
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
scanf("%d", &N);
vector<int> arr(N+1);
for(int i = 1; i<=N; i++){
scanf("%d", &arr[i]);
}
int M;
scanf("%d", &M);
vector<pair<int, int>> testcase(M+1);
for(int i = 1; i<=M; i++){
scanf("%d %d", &testcase[i].first, &testcase[i].second);
}
vector<vector<int>> dp(N+1, vector<int>(N+1));
for(int i = 1; i<=N; i++){
dp[i][i] = 1;
}
for(int i = 1; i<N; i++){
if(arr[i] == arr[i+1]){
dp[i][i+1] = 1;
}
}
for(int i = 2; i<N; i++){
for(int j = 1; j<=N-i; j++){
if(arr[j] == arr[j+i] && dp[j+1][j+i-1] == 1){
dp[j][i+j] = 1;
}
}
}
for(int i = 1; i<=M; i++){
printf("%d\n", dp[testcase[i].first][testcase[i].second]);
}
}
