[백준] 10942 - 팰린드롬?

[문제링크]

10942번: 팰린드롬?

 

0. j ~ j+i 까지의 수가 팰린드롬 수가 되려면

  - j, j+1번 자리의 수가 같아야하며

  - j+1 ~ j+i-1 까지의 수가 팰린드롬 수여야 한다

 

1. 1, 2자리 수에 대해 팰린드롬 수 여부를 계산한다

  - 1자리의 수는 전부 다 팰린드롬 수

  - 두 자리의 수가 연속이라면 팰린드롬 수

 

2. isP[x][y] 배열은 y번째 수부터, x개의 수를 고려했을때 해당 수가 팰린드롬인지 여부를 판단한다

  - isP[10][5] - 5~14의 수가 팰린드롬인지 정보 저장

 

3. 3자리부터 n자리까지 모든 가능한 경우에 대해 팰린드롬 수 여부를 검사한다

  - isP[i-2][j+1] : j+1 ~ j+i-1까지의 팰린드롬 여부

 

4. m개의 입력을 처리하며, 미리 구성된 isP 정보에 따라 1/0 출력 결정

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int[] num = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			num[i]=pint(st.nextToken());
		}
		//2.
		boolean[][]isP = new boolean[N][N];
        
		//1.
		Arrays.fill(isP[0], true);
		for (int i = 0; i < N-1; i++) {
			if(num[i]==num[i+1])isP[1][i]=true;
		}
        
		//3.
		for (int i = 2; i < N; i++) {
			for (int j = 0; j < N-i; j++) {
				if(num[j]==num[j+i]) {
					if(isP[i-2][j+1]) {
						isP[i][j]=true;
					}
				}
			}
		}
        
		//4.
		int m = pint(br.readLine());
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine());
			int s = pint(st.nextToken()), e=pint(st.nextToken());
			sb.append(isP[e-s][s-1]?1:0).append("\n");
		}
		System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면