[백준] 10942 팰린드롬?(G4)

팰린드롬

• 우리 말로 '회문'으로 번역되며 'eye' 'madam'처럼 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말,숫자,문자열 등이다.
• 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시

시간복잡도

1 ≤ N ≤ 2,000 이고, 1 ≤ M ≤ 1,000,000 이므로 최악의 경우 2,000* 1,000,000 = 2,000,000,000 (20억번)의 연산 횟수가 발생한다.

풀이

1. 행과 열이 같으면 항상 팰린드롬이다.
2. S~E 길이가 2이면 두 수가 같아야 팰린드롬이다.
3. S~E 길이가 3이상이면 S와 E번째가 같은지 비교하고 DP[S+1][E-1]값을 비교하면서 팬린드롬이 맞는지 확인한다. (DP[S+1][E-1]값에 접근하기 위해 행을 뒤에서 부터 실행했다.)

DP	0	1	2	3	4	5	6
0	T	F	T	F	F	F	T
1	-	T	F	F	F	T	F
2	-	-	T	F	T	F	F
3	-	-	-	T	F	F	F
4	-	-	-	-	T	F	T
5	-	-	-	-	-	T	F
6	-	-	-	-	-	-	T

코드

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

public class Main {
    static int[] arr;
    static boolean[][] DP;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //수열의 크기
        arr = new int[N]; //수열
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()); //질문의 개수

        DP = new boolean[N][N];
        checkPalindrome(N);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            //배열 맞추기 위해 -1
            int S = Integer.parseInt(st.nextToken()) - 1; //시작
            int E = Integer.parseInt(st.nextToken()) - 1; //끝

            if (DP[S][E])
                sb.append("1\n");
            else
                sb.append("0\n");
        }
        System.out.println(sb);
    }

    public static void checkPalindrome(int N) {
        // S==E는 항상 팰린드롬이다.
        for (int i = 0; i < N; i++) {
            DP[i][i] = true;
        }
        // S,E 길이가 2이면 같아야 팰린드롬이다.
        for (int i = 0; i < N - 1; i++) {
            if (arr[i] == arr[i + 1])
                DP[i][i + 1] = true;
        }
        // S,E 길이가 3이상
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 2 + i; j < N; j++) {
                if (arr[i] == arr[j] && DP[i + 1][j - 1])
                    DP[i][j] = true;
            }
        }
    }
}