[백준 10942] 펠린드롬? -JAVA // le_effort//

배울게 많았던 문제였다.

DP는 다른 알고리즘에 비해 코드 길이가 짧지만 규칙을 찾기가 너무 힘든 것 같다.

 

펠 린드 롬이란 앞으로 읽던 거꾸로 읽던 숫자가 똑같은걸 의미한다

 

M의  최대 크기가 1,000,000으로 크니 DP로 메모제이션을 활용해야 한다.

 

DP [i][j]는

i번째 수부터 j 번째가 펠린드롬인가? 를 의미한다.

 

예를 들면, DP [1][4]는

1번째 수부터 4번째 수 까지가 펠린드롬 인가의 여부를 구하는 것이다

 

펠린드롬을 구하는 방법은 크게 3가지로 나뉜다

1. 길이가 1인 펠린드롬을 구한다.

2. 길이가 2인 펠린드롬을 구한다.

3. 길이가 3 이상인 펠린드롬을 구한다

 

길이가 1인 펠린드롬

일단 길이가 1인 배열의 경우는 무조건 펠린드롬이다.

 

숫자가 하나밖에 없으니 앞에서 읽던 뒤에서 읽던 무조건 일치하기 때문

그러니 먼저 처리를 해준다.

 

for(int i=1; i<=n; i++) {
            dp[i][i] = true;
        }    // 1자리수 펠린드롬은 무조건 true
        

길이가 1, 2 인 펠린드롬은 쉽게 이해 할 수 있을거라고 생각한다.

하지만 길이가 3인 펠린드롬은 나는 이해하는데 시간이 좀 걸렸다.

 

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

 

이 코드를 보고 

2번째 줄에 j <=n-i는 왜 하는 것이며

arr [j] == arr [j+i]에서 j+i는 왜 하는 것이며 

dp [j+1][j+i-1] 은 뭐지?? 이렇게 생각할 수 있다.

 

천천히 풀이를 해보자

일단 위 반복문에서 i는 dp [s][e] 중 e를 차지하며  j는 s를 차지한다.

 

일단 i가 2부터 시작하는 이유는 (3으로 해도 된다)

 

dp [1][3]의 길이가 몇 인지 생각해보자

위에서 dp를 dp [i][j]  i번째~j번째가 펠린드롬인가?라고 정해주었다.

 

dp [1][3]의 길이는 즉 1번째~3번째 이므로 1,2,3으로 길이가 3이다

 

i와 j를 단순히 빼면 (1-3)   그 숫자가 2이지만 길이는 3 임으로 

반복문 i와 j를 통해  dp [i][j]의 길이를 제어할 것임으로 

3번째 길이부터 구해야 하므로 

i=2부터 시작했다

 

그다음 j <=n-i를 분석해보자.

 

일단 길이가 3인 펠린드롬을 다 구하고 다 구했다면

길이가 4인 펠린드롬을 구하고 다 구했다면

길이가 5인 펠린드롬을 구하고  

 

이런 식으로 흘러간다

 

이 반복문에서

dp [s][e]는 s부터 e까지의 펠린드롬 여부 임으로 

s는 무조건 e보다 작아야 한다.

 

위 예제에서 배열의 길이는 7 , 그리고 지금 구하는 단계의 길이가 3인 경우 

[1][3], [2][4] [3][5] [4][6] [5][7]을 다 구해야 한다.

 

[6][7] 은 길이가 2 임으로 구할 필요가 없다.

 

위 반복문에서 i는 dp [s][e] 중  e를 차지하고 j는 s를 차지한다.

즉 최대길이 - 지금 구하는 길이를 하면 시작 범위의 최대 범위가 나온다.(위의 예제에서는 5)

 

그다음  예를 들어 1~5까지의 펠린드롬의 여부를 구하기 위해서는

 

1. 일단 arr [1]과 arr [5]가 같아야 하며

1~5 사이에 있는 arr [2] arr [3] arr [4]가 펠린드롬을 이뤄야 한다

 

3번째 줄은 그를 의미한다.

 

그리고 시간 초과가 나는 경우가 있는데

이런 경우 M의 모든 케이스당 1 아니면 0을 출력해야 하는데

나는 맨 처음에 System.out.println으로 했지만 시간 초과를 받았다.

 

이런 단순한 수많은 출력은 시간을 많이 잡아먹으므로

StringBuilder나 BufferedWriter를 통해 해결해야 한다.

 

전체 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int s,e;
    static int arr[];
    static boolean dp[][];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        dp = new boolean[n+1][n+1];
        String[] t = br.readLine().split(" ");
        
        for(int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(t[i-1]);
        }
        
        m = Integer.parseInt(br.readLine());
        
        for(int i=1; i<=n; i++) {
            dp[i][i] = true;
        }    // 1자리수 펠린드롬은 무조건 true
        
        for(int i=1; i<n; i++) {
            if(arr[i] == arr[i+1]) {
                dp[i][i+1] = true;
            }
        }    //  2자리수 펠린드롬은 배열이 같으면 true
        
        for(int i=2; i<n; i++) {
            for(int j=1; j<=n-i; j++) {
                if(arr[j] == arr[j+i] && dp[j+1][j+i-1]) {
                    dp[j][j+i] = true;
                }
            }
        }
        
        for(int i=0; i<m; i++) {
            String[] tt = br.readLine().split(" ");
            s = Integer.parseInt(tt[0]);
            e = Integer.parseInt(tt[1]);
            if(dp[s][e]) {
                sb.append(1+"\n");
            }
            else {
                sb.append(0+"\n");
            }
        }
        System.out.println(sb);
    }
}