팰린드롬?

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

10942번: 팰린드롬?

 

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

 - S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
 - S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
 - S = 3, E = 3인 경우 1은 팰린드롬이다.
 - S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력 1 

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 1 

1
0
1
1

 

문제회고

다시 풀어도 틀린 문제... 이런 내 자신한테 화가난다.
우선 주어진 입력 범위가 2000 이므로 2중 루프 이상을 하면 안되므로 재귀와 같은 방식은 시간초과가 발생할 것이다. 경험상 재귀냄새가 물씬나는데 입력값이 높으면 보통 dp를 생각해보면 상당부분 적중했다.

dp를 어떻게 적용할 수 있을지 고민해보면, 
예제에서 주어진 입력 값이 N = 7, [1, 2, 1, 3, 1, 2, 1] 이 주어졌다.
구간별 생각해볼 필요가 있다. 구간을 크게 3부분으로 나눠보면, 구간 1인 경우, 2인 경우, 3이상인 경우이다.
1인경우는 무조건 팰린드롬이므로 별도로 처리를 해준다.
2인경우는 인접한 부분을 비교해서 별도로 처리를 해준다.
3이상인 경우
이론적으로는 3 ~ 7 구간까지를 팰린드롬이 성립한지를 확인하면 된다.

코드레벨에서 생각해보면
첫 루프의 구간을 2 ~ 6까지를 크게 잡아줄 수 있다. -> i
두 번째 루프의 구간을 1 ~ ( 7 - i ) 를 해주면 된다. -> j
이렇게 하며 j = 1, (j + i ) = 3 즉 (1 ~ 3) 부터 (5 ~ 7) 까지 3구간 전체를 체크해줄 수 있다..이렇게 연쇄적으로 4, 5, 6, 7 구간을 확인해가는 것이다. 설명이 살짝 엉성한데 이부분은 직접 써보면 이해가 될 것이다.
여기서 우리는 2구간까지 팰린드롬을 이미 구했다.
3구간에서는 첫 수와 마지막 수의 일치를 비교하고, 일치하면 (처음 시작 수 인덱스 + 1), (마지막 수 인덱스 - 1)가 팰린드롬인지를 dp테이블에서 true인지만 판단하면 끝이다. 더 파고 들어갈 필요가 없다.

// 코드

import java.util.*;
import java.io.*; 
 
 
public class Main { 
  
  static int N, M;
  static int[] arr;
  static boolean[][] dp; 
  
  
  // main
  public static void main(String[] args) throws Exception{
    
    // Please Enter Your Code Here
    StringBuilder sb   = new StringBuilder();
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    
    N   = Integer.parseInt(br.readLine());
    dp  = new boolean[N + 1][N + 1];
    arr = new int[N + 1];
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    for( int i = 1; i < N + 1; ++i ) arr[i] = Integer.parseInt(st.nextToken());
    
    isPalindrome();
    
    M = Integer.parseInt(br.readLine());
    while ( M --> 0 ) { 
      st    = new StringTokenizer(br.readLine());
      int S = Integer.parseInt(st.nextToken());
      int E = Integer.parseInt(st.nextToken());
      
      sb.append( (dp[S][E] ? 1 : 0) + "\n" );
    }
     
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  
  // 팰린드롬 검증
  static void isPalindrome() {
    for ( int i = 1; i < N + 1; ++i) dp[i][i] = true;
    for ( int i = 1; i < N; ++i ) if ( arr[i] == arr[i + 1] ) dp[i][i + 1] = 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; 
  }
  
} 

 

// 복습

import java.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static int N, M;
  static int[] arr;
  static boolean[][] dp;
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringTokenizer st = null;
    
    N   = Integer.parseInt( br.readLine() );
    st = new StringTokenizer( br.readLine() );
    arr = new int[N + 1];
    dp  = new boolean[N + 1][N + 1];
    for ( int i = 1; i <= N; ++i ) arr[i] = Integer.parseInt( st.nextToken() ); 
    
    // 1. dp테이블을 만든다.
    MakeDpTable(); 
    
    StringBuilder sb = new StringBuilder();
    M = Integer.parseInt( br.readLine() ); 
    
    while ( M --> 0 ) { 
      int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); 
      sb.append(dp[info[0]][info[1]] ? 1 : 0).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close(); 
  } 
  
  
  static void MakeDpTable() {
    
    // 구간이 1인 경우
    for ( int i = 1; i < N + 1; ++i ) dp[i][i] = true;
    
    // 구간이 2인 경우
    for ( int i = 1; i < N; ++i  )  if ( arr[i] == arr[i + 1] ) dp[i][i + 1] = true; 
    
    // 구간이 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; 
  }
  
}