(22.08.09) (Baekjoon) 10942.팰린드롬?

10942번: 팰린드롬?

시간 제한 0.5초

(

• Java 8: 2.5 초
• PyPy3: 1.5 초
• Java 8 (OpenJDK): 2.5 초
• Java 11: 2.5 초
• PyPy2: 1.5 초
• Kotlin (JVM): 2.5 초

)

메모리 제한 : 256MB

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• 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을 출력한다.

예제 입력 1 복사

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 1 복사

1
0
1
1

 

단순하게 팰린드롬을 하나하나 검사하는 걸로는 시간초과가 나는 문제다.

이 문제의 키 포인트는 DP 배열의 길이에 있다.

for문을 3번 돌리게 된다(3중 for문이 아니라 3번의 for문을 사용한다)

 

1번 for : 1~n까지

dp[i][i] = 1;

한 개의 글자는 어차피 무조건 팰린드롬이다.

for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}

 

 

2번째 for : 1~n-1

i번째 수와 i+1번째 수가 같으면 팰린드롬이다.

for (int i = 1; i <= n-1; i++) {
			if(ar[i] == ar[i+1]) dp[i][i+1] = 1;
		}

 

3번째 for : 

이 for문은 이중 for문을 사용한다.

2~n-1을 보는 i for문 안에

1~n-i를 보는 j for문을 보게 된다.

이 안에서의 dp[i][j]는 아래 두 조건을 모두 만족하면 1이 된다.

1) dp[j+1][j+i-1] == 1 ==> 시작 인덱스 +1번째 수 ~ 끝 인덱스 -1번째 수 부분이 팰린드롬이 성립된다

2) ar[j] == ar[j+i] ==> 시작 숫자와 끝 숫자가 같다.

 

위 두 조건을 만족하면 결국 팰린드롬이 된다!

for (int i = 2; i < n; i++) {
			for (int j = 1; j <= n-i; j++) {
				if(ar[j] == ar[j+i] && dp[j+1][j+i-1] == 1) dp[j][j+i] = 1;
			}
		}

 

 

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

public class Main {

	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] ar = new int[n+1];
		int[][] dp = new int[n+1][n+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			ar[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}
		for (int i = 1; i <= n-1; i++) {
			if(ar[i] == ar[i+1]) dp[i][i+1] = 1;
		}
		
		for (int i = 2; i < n; i++) {
			for (int j = 1; j <= n-i; j++) {
				if(ar[j] == ar[j+i] && dp[j+1][j+i-1] == 1) dp[j][j+i] = 1;
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			sb.append(dp[a][b]).append("\n");
		}
		
		System.out.println(sb);
	}

}

출근하면서 하자니 영 쉽지 않다

그래도 조금만 더 해봐야겠다