첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다.
팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
dp를 사용해서 문제를 해결
2차원 배열을 만들어서
천천히 생각해보면 어렵지 않게 풀 수 있는 문제였다!
*StringBuilder
가 아니라 System.out.println()
을 사용하니깐 시간 초과가 발생
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, S, E;
static int[] arr;
static boolean[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
dp = new boolean[N + 1][N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
solve();
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
sb.append(dp[S][E]==true ? "1\n" : "0\n");
}
System.out.println(sb);
}
public static void solve() {
for (int i = 1; i <= N; i++)
dp[i][i] = true;
for (int i = 1; i <= N - 1; i++)
if (arr[i] == arr[i + 1]) dp[i][i + 1] = true;
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])
dp[j][j + i] = true;
}
}
}
}