[백준 Java] 10942 팰린드롬?

<문제 링크> 자바 10942 팰린드롬 dp 

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

10942번: 팰린드롬?

시간제한이 0.5초이고 메모리 제한이 커서 dp를 이용해서 저장해 두고 테스트 케이스에 대해서 계산된 값을 출력해야겠다고 생각했다.

dp 테이블에는 팰린드롬이라면 1을 저장하고 아니면 0을 저장하였다.

포인트라고 생각한 아이디어는 i ~ j 까지가 팰린드롬인지를 확인하기 위해서 input[ i ]와 input[ j ]를 비교하고 i+1과 j-1까지가 팰린드롬 인지를 확인하면 된다.

 

예를 들어 만약 테스트 케이스가 " 1 2 1 3 1 2 1 "이고 이의 결과를 테이블 형식으로 나타내면 아래와 같다 

 

행 단위로 다음 줄로 넘어가는 것이 아니라

열 단위로 계산하면서 넘어간다.

그래서 각 dp 배열 칸 arr [i][j] 안에는 i에서부터 j까지가 팰린드롬 확인하는 값이 들어간다.

 

길이가 1이라면 팰린드롬 이므로 1

길이가 2라면 앞과 뒤만 확인 하여 팰린드롬인지 판별하고

길이가 3 이상이라면 제일 앞과 뒤만 확인하고 arr[i+1][j-1]을 확인하여 팰린드롬 인지 확인할 수 있다. (arr[i+1][j-1] 에는 i+1 ~ j-1까지가 팰린드롬인지 확인한 결괏값이 들어있으므로)

 

 

 

<코드>

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();


        int n = Integer.parseInt(br.readLine());
        int arr[][] = new int[n+1][n+1];
        int input[] = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int j=1;j<=n;j++){
            int temp = Integer.parseInt(st.nextToken());
            input[j]=temp;
            for(int i=1;i<=j;i++){
                if(i==j)arr[i][j]=1;
                else if(j-i==1) arr[i][j] = (input[j]==input[i])?1 : 0;
                else {
                    arr[i][j] = (input[j]==input[i] && arr[i+1][j-1]==1)?1 : 0;
                }
            }
        }

        int TC = Integer.parseInt(br.readLine());
        while(TC --> 0 ){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(arr[a][b]).append("\n");
        }

        System.out.println(sb);
    }
}