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

10942번: 팰린드롬?

문제

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

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E로 나타낼 수 있으며, 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

 

시작이 반이라고, 오늘은 알고리즘 하루 1문제 풀기 두 번째 날입니다. (짝짝짝)

이번 문제는 그냥 팰린드롬인지 아닌지 판별만 해서는 풀기 어려운 문제입니다. 질문의 갯수가 굉장히 많기 때문입니다. `셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.`에서 보듯이 1000000개의 질문이 주어지고 시간 제한은 그에 비해 빡센 편입니다. 그렇다면 어떻게 풀 수 있을까요? 바로 다이나믹 프로그래밍을 이용해서 풀 수 있습니다.

이런 접근법은 해보기 전에는 생각해내기 어려울 수 있지만 몇 번 해보면 어떤 경우에 이런 접근법을 사용하면 좋을지 알 수 있습니다.

 

먼저 dp배열을 만들어두고, 이를 -1로 초기화 해둡니다. 이번 문제에서도 index는 1부터 n까지로 설정했는데요, dp 문제를 풀 때 이렇게 문제를 푸시는 분들이 많은 것 같아요. 그 이후 isPalindrome 함수에서 판별을 하게 됩니다.

핵심은 dp 배열인데요. 2차원 배열인 dp 배열은 start 인덱스와 end 인덱스 까지의 범위를 나타내준다고 생각하면 됩니다.

dp[start][end] <- start 인덱스부터, end 인덱스까지가 팰린드롬인지 검사한 결과를 보관

이렇게 검사를 해가면서, 중간중간 검사했던 결과를 저장해두는 메모이제이션 방식을 이용한 문제 풀이입니다!

처음에 초기화해두었던 -1이 아닌 경우는, 이미 검사를 했던 범위라는 걸 알 수 있고 이런 경우에는 추가적인 검사를 하지 않고 저장해뒀던 결과를 return하게 됩니다.

 

#include <iostream>
using namespace std;

int arr[2001];
int dp[2001][2001];

int isPalindrome(int s, int e) {
    if (dp[s][e] != -1) {
        return dp[s][e];
    }

    if (s == e) {
        return dp[s][e] = 1;
    }
    
    if (s == e - 1) {
        return arr[s] == arr[e] ? dp[s][e] = 1 : dp[s][e] = 0;
    }
    
    return arr[s] == arr[e] ? dp[s][e] = isPalindrome(s + 1, e - 1) : dp[s][e] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int j = 1; j <= n; j++) {
            dp[i][j] = -1;
        }
    }

    int m;
    cin >> m;
    while (m--) {
        int s, e;
        cin >> s >> e;

        cout << isPalindrome(s, e) << '\n';
    }

    return 0;
}