[BaekJoon] 10942 팰린드롬?

1.  문제 링크

https://www.acmicpc.net/problem/10942

2.  문제

요약

• 홍준이는 자연수 N개를 칠판에 적고, 그 다음 명우에게 질문을 총 M번 합니다.
• 각 질문은 두 정수 S와 E로 나타낼 수 있고, S번째 수부터 E번째까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 합니다.
• 자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 2,000보다 작거나 같은 수열의 크기 N이 주어지고 두 번째 줄에는 100,000보다 작거나 같은 자연수인 홍준이가 칠판에 적은 수 N개가 주어지며. 세 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 홍준이가 한 질문의 개수 M이 주어지고 네 번째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄씩 주어집니다.
  • 1 ≤ S ≤ E ≤ N
• 출력: 총 M개의 줄에 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라 출력합니다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력합니다.

3.  소스코드

투포인터를 이용한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Reader scanner = new Reader();
	static int N, M, S, E;
	static int[] series;
	static void input() {
		N = scanner.nextInt();
		series = new int[N];
		for(int index = 0; index < N; index++) series[index] = scanner.nextInt();
		M = scanner.nextInt();
		for(int question = 0; question < M; question++) {
			S = scanner.nextInt();
			E = scanner.nextInt();
			isPalindrome();
		}
	}
	
	static void isPalindrome() {
		if(S == E) {
			sb.append(1).append('\n');
			return;
		}
		for(int start = S - 1, end = E - 1; start < end; start++, end--) {
			if(series[start] != series[end]) {
				sb.append(0).append('\n');
				return;
			}
		}
		sb.append(1).append('\n');
		return;
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

다이나믹 프로그래밍을 이용한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
	static Reader scanner = new Reader();
	static int N, M, S, E;
	static boolean[][] palindrome;
	static int[] series;
	static void input() {
		N = scanner.nextInt();
		series = new int[N + 1];
		for(int index = 1; index <= N; index++) series[index] = scanner.nextInt();
		findAllPalindrome();
		M = scanner.nextInt();
		for(int question = 0; question < M; question++) {
			S = scanner.nextInt();
			E = scanner.nextInt();
			if(palindrome[S][E]) sb.append(1).append('\n');
			else sb.append(0).append('\n');
		}
	}
	
	static void findAllPalindrome() {
		palindrome = new boolean[N + 1][N + 1];
		for(int start = 1; start <= N; start++) palindrome[start][start] = true;
		for(int start = 1; start < N; start++) {
			if(series[start] == series[start + 1]) palindrome[start][start + 1] = true;
		}
		for(int len = 3; len <= N; len++) {
			for(int start = 1; start + len - 1 <= N; start++) {
				if(series[start] == series[start + len - 1] && palindrome[start + 1][start + len - 2])
					palindrome[start][start + len - 1] = true;
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}