[JAVA] 백준 (골드4) 10942번 팰린드롬?

링크

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

---

문제 설명

정답률 30.327%
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.***

입력 예제

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

---

출력 예제

1
0
1
1

---

풀이

최대 100,000개의 수열에서 모든 구간에서의 팰린드롬 여부를 확인해야 한다. 길이에 따라 생각해보면 다음과 같다.

• 길이가 1일 때 -> 무조건 팰린드롬
• 길이가 2일 때 -> 인접 수가 같을 때 팰린드롬

길이가 2보다 커질 때를 생각해보면

• 1, 2, 1
• 1, 2, 2, 1
• 1, 2, 3, 2, 1
  ...

규칙성을 찾을 수 있는데 다음의 조건을 만족해야 한다.

1. 수열의 첫번째와 마지막 수가 같을 때
2. 첫번째와 마지막 수를 제외한 수열이 팰린드롬일 때

따라서 dp배열을 다음과 같이 정의한다.

dp[i][j]: i번째부터 j번째까지 수열의 팰린트롬 여부를 저장

길이가 1이나 2일 때는 다음과 같이 간단하게 구현한다.

//길이가 1일 때
for (int i = 1; i <= N; i++) {
    dp[i][i] = 1;  
}

//길이가 2일 때
for (int i = 1; i < N; i++) {
    if (seq[i] == seq[i + 1]) {
        dp[i][i + 1] = 1;
    }
}

길이가 2보다 커질 때는 수열의 길이가 7이라면 부분 수열의 모든 구간은 $[1, 3], [2, 4], ..., [5, 7], [1, 4], ..., [4, 7], ..., [1, 7]$이 되고, 이중 반복문으로 구현하면 다음과 같다.

//길이가 3 이상일 때
for (int len = 2; len < N; len++) {
    for (int s = 1; s <= N - len; s++) {
        int e = s + len;
        if (seq[s] == seq[e] && dp[s + 1][e - 1] == 1) {
            dp[s][e] = 1;
        }
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] seq = new int[N + 1];
        int[][] dp = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            dp[i][i] = 1;  //길이가 1일 때
        }

        //길이가 2일 때
        for (int i = 1; i < N; i++) {
            if (seq[i] == seq[i + 1]) {
                dp[i][i + 1] = 1;
            }
        }

        //길이가 3 이상일 때
        for (int len = 2; len < N; len++) {
            for (int s = 1; s <= N - len; s++) {
                int e = s + len;
                if (seq[s] == seq[e] && dp[s + 1][e - 1] == 1) {
                    dp[s][e] = 1;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            sb.append(dp[S][E]).append("\n");
        }

        System.out.println(sb);
    }
}