[BOJ] 10942:팰린드롬?

0. 문제

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

10942번: 팰린드롬?

 

1. 문제분석

- 이전의 상태(현재 문자열에서 양 끝의 문자열을 제외한 사이의 문자열이 팰린드롬인지)에 따라서 현재의 상태를 결정(현재의 문자열이 팰린드롬인지)한다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다.

- dp[i][j] : 주어진 문자열 중, i번째 문자부터 j번째 문자까지로 이루어진 부분 문자열이 팰린드롬인지 (boolean)

 

2. 주의할 점

- 팰린드롬을 판단하는 부분 문자열의 길이에 따라서 dp 배열을 전처리 해주어야 한다. 

- 부분 문자열의 인덱싱이 헷갈릴 수 있으니 유의해야 한다.

- 출력이 잦다보니, 이번에도 마찬가지로 StringBuilder를 사용해 시간을 줄여야 한다.

 

3. 소스코드(Java)

// boj 10942 펠린드롬?
// dp

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

public class boj_10942 {
    static int n, m, s, e;
    static int[] numbers;
    static boolean[][] isPalindrome;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        n = stoi(st.nextToken());
        numbers = new int [n];
        isPalindrome = new boolean [n][n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) {
            numbers[i] = stoi(st.nextToken());
            isPalindrome[i][i] = true;
            if (i > 0 && numbers[i-1] == numbers[i]) isPalindrome[i-1][i] = true;
        }
        for (int l = 3; l <= n; ++l) {
            for (int i = 0; i <= n - l; ++i) {
                if (numbers[i] == numbers[i + l - 1] && isPalindrome[i + 1][i + l - 2])
                    isPalindrome[i][i + l - 1] = true;
            }
        }
        m = stoi(br.readLine());
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            s = stoi(st.nextToken()) - 1;
            e = stoi(st.nextToken()) - 1;
            sb.append(isPalindrome[s][e] ? 1 : 0).append('\n');
        }
        System.out.print(sb);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

4. 여담

- 코테에서 마주했던 문제와 매우 비슷한 문제여서 문제 풀이 방법을 그대로 가져왔다. (코테는 떨어졌지만..ㅠ)