[BOJ 10942] 펠린드롬? - JAVA, Gold4

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

10942번: 팰린드롬?

사용한 알고리즘: DP

 

풀이전략

펠린드롬수는 쉽게 말해서 앞으로 읽으나 뒤로 읽으나 같은 수를 뜻한다.

 

문제 해결 접근 방식으로

질문이 주어질 때마다 해당 수가 펠린드롬 수인지 파악하려고 한다면

최악의 경우 1,000,000번의 펠린드롬 수 판단 연산을 수행해야 한다.

 

수열의 크기가 최대 2000까지 가능하므로

최악의 경우 2000 * 1,000,000 = 2,000,000,000(20억)번 연산이 필요하다.

이는 JAVA가 초당 1억번 연산하므로 20초가 걸려 시간 초과가 발생한다.

 

따라서  다른 방법이 필요한데 나는 다이나믹 프로그래밍을 사용해 풀이했다.

dp[i][j]는 입력받은 배열에서 i번째 인덱스에서 j번재 인덱스까지의 수가

펠린드롬 수이면 true를, 펠린드롬 수가 아니면 false를 저장하는 이중 배열이다.

 

수열의 크기 N은 최대 2000까지 가능하다 했으므로

dp의 크기를 int dp[][] = new int[2001][2001]; 로 선언하고,

이는 펠린드롬 수를 구하기 위한 연산으로 2,000 * 2,000 = 4,000,0000 번만이 필요함을 뜻한다.

 

따라서 이전의 BruteForce 방식에 비해 월등히 성능이 좋은 방식으로

미리 주어진 수에서 특정 범위의 수가 펠린드롬 수인지 아닌지 결정해둘 수 있다.

 

입력으로 주어진 수열이 담긴 배열을 list[] 라고 하면 팰린드롬 탐색과정은 다음과 같다.

 

1) 수가 하나만 있으면 펠린드롬 수 ( ex) 1, 2, 3, ... )

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

수가 하나만 있는 경우는 반드시 펠린드롬 수 이므로 dp[i][i]를 true로 정의한다.

 

2) 연속된 두 수가 같으면 펠린드롬 수 ( ex) 11, 22, 33, ... )

for(int i=1;i<N;++i){
    if(list[i]==list[i+1]) dp[i][i+1]=true;
}

연속된 두 개의 수가 같은 값을 가지면 펠린드롬 수이므로 d[i][i+1]을 true로 정의한다.

 

3) d[j+1][j+i-1]=true 면서 list[j] = list[j+i] 면 펠린드롬 수

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

이후 입력값으로 start와 end를 받고

dp[start][end]를 사용해 해당 수가 펠린드롬 수인지 아닌지 판단하여 원하는 값을 출력하면 된다.

 

제출코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static boolean dp[][] = new boolean[2001][2001];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int list[] = new int[N+1];
        for(int i=1;i<=N;++i){
            list[i]=Integer.parseInt(st.nextToken());
        }

        for(int i=1;i<=N;++i){
            dp[i][i]=true;
        }
        for(int i=1;i<N;++i){
            if(list[i]==list[i+1]) dp[i][i+1]=true;
        }

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

        int M = Integer.parseInt(br.readLine());
        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            if(dp[start][end]) bw.write(1+"\n");
            else bw.write(0+"\n");
        }
        bw.flush();
        bw.close();
    }
}