[ 백준 10942 ] 팰린드롬 ? (C++)

백준의 팰린드롬?(10942) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

타 사이트에서 이 문제와 똑같은 문제를 해결하고 포스팅 해놓은 글이 있다.

풀이 자체가 완전히 똑같기 때문에 풀이를 해당 포스팅 글로 대체하겠다.

[ 팰린드롬 풀이 바로가기 ]

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
#define MAX 2010
using namespace std;
 
int N;
int Arr[MAX];
bool DP[MAX][MAX];
vector<pair<int, int>> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
    int K; cin >> K;
    for (int i = 0; i < K; i++)
    {
        int a, b; cin >> a >> b;
        V.push_back(make_pair(a, b));
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++) DP[i][i] = true;
    for (int i = 1; i < N; i++)
    {
        if (Arr[i] == Arr[i + 1]) DP[i][i + 1] = true;
    }
 
    for (int Len = 3; Len <= N; Len++)
    {
        for (int Start = 1; Start <= N - Len + 1; Start++)
        {
            int End = Start + Len - 1;
            if (Arr[Start] == Arr[End] && DP[Start + 1][End - 1] == true)
            {
                DP[Start][End] = true;
            }
        }
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        cout << DP[V[i].first][V[i].second] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}