[백준] Q10942 팰린드롬? Gold III

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

10942번: 팰린드롬?

 

1. 문제 유형 및 이해

dp

 

N개의 숫자가 있고 M개의 질문을 한다.

각 질문은 (Start, End)로 이루어져 있어서 S번째 수 부터 E번째 수까지 팰린드롬인지를 묻는 문제입니다.

 

처음 문제를 이해할 때, S부터 E까지의 수를 Dequeue에 넣어 팰린드롬인지 확인할까? 라는 생각을 했다가

어떤 질문(query)들에 대해서 "빠르게" 답했던 문제들을 복기해보면 미리 data를 쌓아두고

간단한 계산을 통해 대답을 했던 것을 기억했습니다.

가장 기본적인 연속된 수 누적합 문제의 풀이를 떠올렸습니다.

 

이후 팰린드롬의 특성을 생각해볼 때, 어떤 String에서

가장 첫 부분과 마지막 부분이 같을 때 가운데 부분이 팰린드롬이라면 팰린드롬은 당연합니다.

이를 이용해 dynamic programming으로 풀어보았습니다.

 

2. 문제 접근

무언가를 빠르게 대답하기 위해 미리 적어놓아야 겠다.(memoization)

또한 이를 이용해서 간단한 계산을 통해 답해야겠다. 라는 점과

[S, E]에서 

string[S] == string[E] 일때 만약 [S+1,E-1]이 팰린드롬이라면 [S,E]도 팰린드롬이라는 작은 문제를 풀어

큰 문제를 해결할 수 있다는 점에서 dp라고 생각하고 접근하였습니다.

 

 Top - Down 방식 풀이 (code에서 find함수)

어떤 S,E가 들어올 때

1. S == E라면 한 글자라 팰린드롬이다. return true;

2. S와 E를 비교한다.

   2.1 같지 않다면 팰린드롬이 아니다. return false;

   2.2 [S+1,E-1]을 비교해본다.

2.2의 경우 다시 1로 돌아가서 풀어봅니다.

 

새롭게 Bottom-up 방식 풀이를 생각해봅시다(code에서의 solve 함수)

1. 한 글자는 모두 팰린드롬이다.    (당연한 사실)

2. 두글자일때 인접한 값들이 같다면 팰린드롬이다.  (당연한 사실)

3. 세글자 이상부터는 위와 같습니다. 

   다만 n글자 일 때 우리는 그 전에 1~n-1글자를 모두 구해놓았기 때문에 바로 구할 수 있습니다.

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int[] numbers;
    static int N;
    static boolean dp[][];
    static BufferedReader br;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        StringBuilder sb= new StringBuilder();
        N = Integer.parseInt(br.readLine());
        numbers =Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        dp = new boolean[numbers.length][numbers.length];
        for(int i =0;i<numbers.length;i++)dp[i][i] = true;
        int M = Integer.parseInt(br.readLine());
        for(int q =0;q<M;q++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken())-1;
            int e = Integer.parseInt(st.nextToken())-1;
            sb.append(find(s,e)?1:0).append('\n');
        }
        System.out.print(sb.toString());
    }

    public static boolean find(int start, int end){
        //마지막 종료조건
        if(start >= end) return true;
        if(numbers[start] != numbers[end]) return false;
        if(dp[start][end]== true) return true;
        if(numbers[start] == numbers[end]){
            dp[start][end] = find(start+1,end-1);
        }
        return dp[start][end];
    }
}