[C++] BOJ 10942: 팰린드롬?

2024년 1월 4일

문제

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

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

각 질문은 두 정수 $$S$$ 와 $$E$$ ( $1 \leq S \leq E \leq 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$$ 개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 $$N$$ ( $1 \le N \le 2\,000$ )이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 $$N$$ 개가 순서대로 주어진다. 칠판에 적은 수는 $100\,000$ 보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 $$M$$ ( $1 \le M \le 1\,000\,000$ )이 주어진다.

넷째 줄부터 $$M$$ 개의 줄에는 홍준이가 명우에게 한 질문 $$S$$ 와 $$E$$ 가 한 줄에 하나씩 주어진다.

출력

총 $$M$$ 개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 $$1$$ , 아닌 경우에는 $$0$$ 을 출력한다.

배열의 $$S$$ 번째 수와 $$E$$ 번째 수가 같고 $$S+1$$ 번째 수부터 $$E-1$$ 번째 수까지가 팰린드롬이면 $$S$$ 번째 수부터 $$E$$ 번째 수까지 또한 팰린드롬이기 때문에, 2차원 DP를 작성하면 됩니다.

$$S = E-1$$ 인 경우에 유의합시다.

c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int arr[2005];
bool dp[2005][2005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    
    for(int i = N; i >= 1; i--) {
        dp[i][i] = true;
        dp[i][i+1] = (arr[i] == arr[i+1]);
        
        for(int j = i+2; j <= N; j++) {
            if(arr[i] != arr[j]) continue;
            
            dp[i][j] = dp[i+1][j-1];
        }
    }
    
    cin >> M;
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        
        cout << dp[a][b] << "\n";
    }
    return 0;
}