[백준] 10942번 : 팰린드롬?

인간몽쉘김통통·2024년 7월 6일

DP 백준 알고리즘

백준

목록 보기

73/92

문제

이해

N 크기의 수열이 주어지고 해당 수열의 S에서 M까지의 수가 팰린드롬인지 구하는 문제입니다.

N은 최대 2000, M은 최대 1000000입니다.

접근

팰린드롬은 중간을 기준으로 좌우 대칭인 수 또는 문자열을 말합니다. 예를 들어, (1, 2, 1), (1, 2, 3, 2, 1), (1) 과 같이 대칭인 경우가 팰린드롬에 해당합니다.

주어진 수열이 팰린드롬인지 판단해야 합니다. 직관적인 방법으로는 완전탐색이 있습니다. 좌우 대칭이기 때문에 양 끝에 포인터를 두고 각 수를 비교하면서 팰린드롬인지 판단할 수 있습니다. 완전탐색의 시간복잡도를 분석하면, M은 1000000이고 N은 최대 2000입니다. 1회 탐색에 최대 (2000 / 2) => 1000이 걸리기 때문에 전체 과정의 시간복잡도는 1000 x 1000000 = 10억입니다. 따라서, 완전탐색은 불가능해보입니다.

수정 연산이 없는 전제에서 수 많은 조회 연산을 요구하는 경우에는 중복된 연산을 제거하기 위해 메모이제이션을 활용하기도 합니다. 또한, 팰린드롬의 특징을 보면 팰린드롬은 좌우대칭이기 때문에 팰린드롬의 내부 문자열 역시 팰린드롬입니다.

(1 2 3 4 3 2 1) 에서 양 끝을 제거해도 (2 3 4 3 2)로 팰린드롬입니다.

이를 미루어보아 본 문제는 메모이제이션을 활용하는 DP로 풀이할 수 있음을 알 수 있습니다.

점화식은 다음과 같습니다.

DP[i][j] =
1. arr[i] == arr[j] 이라면 DP[i+1][j-1]
2. arr[i] != arr[j] 이라면 0

풀이

Top-Down으로 코드를 작성했습니다.

private static int solve(int a, int b) {
        if (dp[a][b] != -1) {
            return dp[a][b];
        }

        if (a == b) {
            return dp[a][b] = 1;
        }

        if (a + 1 == b) {
            if (arr[a] == arr[b]) {
                return dp[a][b] = 1;
            }
        }

        if (arr[a] != arr[b]) {
            return dp[a][b] = 0;
        } else {
            return dp[a][b] = solve(a + 1, b - 1);
        }
    }

위 코드는 DP를 수행하는 메소드입니다. 상단부터 분기에 대한 설명은 다음과 같습니다.
1. dp[a][b]의 값이 메모이제이션되었다면 그대로 반환
2. a와 b가 같다면 무조건 팰린드롬
3. a와 b가 이웃해있다면 값을 비교하여 반환
4. 나머지의 경우에는 점화식에 따라 값을 반환

코드

package baekjoon;

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

public class prob10942_2 {
    static StringBuilder sb = new StringBuilder();
    static int[][] dp;
    static int N, M;
    static int[] arr;
    static StringTokenizer st = null;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }
        arr = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);

            sb.append(solve(a, b)).append("\n");
        }

        System.out.println(sb.toString());
    }

    private static int solve(int a, int b) {
        if (dp[a][b] != -1) {
            return dp[a][b];
        }

        if (a == b) {
            return dp[a][b] = 1;
        }

        if (a + 1 == b) {
            if (arr[a] == arr[b]) {
                return dp[a][b] = 1;
            }
        }

        if (arr[a] != arr[b]) {
            return dp[a][b] = 0;
        } else {
            return dp[a][b] = solve(a + 1, b - 1);
        }
    }
}