백준 10942 - 팰린드롬?

 

 

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 숫자가 주어지고 M개의 질문이 주어진다.

이때, M개의 질문에는 시작점(S)과 끝점(E)이 있고 해당 구간이 팰린드롬이 되는지 판단하면 되는 문제이다.

 

개념은 간단하다.

S, E 에서 출발하는 투 포인터를 통해 두 수가 같으면 한 칸씩 전진하고 그렇지 않으면 팰린드롬이 아니게 된다.

하지만, 이 방법은 구현이 간단하지만 시간이 오래 걸린다.

즉, 시간초과가 발생할 것이다.

 

따라서 다른 접근법이 필요하다.

DP를 통해 포함되는 구간의 팰린드롬 여부를 알수 있다면, 더 이상 비교연산을 진행하지 않아도 된다.

팰린드롬이 될 수 있는 경우는 총 세 가지이다. 

1. 하나의 수로 이루어진 팰린드롬
2. Nums[i] == Nums[i+1], 두 개의 수로 이루어지고 서로 같은 수
3. Nums[S++] == Nums[E--], 세 개 이상의 수로 이루어진 팰린드롬

 

1, 2 번째 방법은 입력과정에서 구할 수 있다.

1번은 항상 참이다.

2번은 자신 이전의 수와 같은지 여부를 확인하면 된다.

for (int i = 1; i <= N; i++)
{
    DP[i][i] = true;
    cin >> Nums[i];

    if (i > 1)
    {
        if (Nums[i] == Nums[i - 1])
        {
            DP[i - 1][i] = true;
        }
    }
}

 

 

3번의 경우만 구해내면 문제는 해결된다.

슬라이딩 윈도우처럼 구간의 길이를 정한 뒤, S와 E가 하나씩 더 전진한 구간의 팰린드롬 여부를 확인하며 DP를 채워나가면 된다.

파란색 부분이 팰린드롬인지 확인하기 위해서는 S와 E가 하나씩 전진한 [1, 3, 1]이 팰린드롬인지 확인하면 된다는 뜻이다.

단, Nums[S]와 Nums[E]가 같을 때만 성립된다.

for (int i = 2; i < N; i++)
{
    int Start = 1;
    int End = Start + i;

    while (End <= N)
    {
        if (DP[Start + 1][End - 1])
        {
            if (Nums[Start] == Nums[End])
            {
                DP[Start][End] = true;
            }
        }

        Start++;
        End++;
    }
}

 

이후, DP배열에서 참조하여 결과를 출력하면 된다.

cin >> M;

for (int i = 0; i < M; i++)
{
            int S, E;
    cin >> S >> E;

    if (DP[S][E]) cout << 1 << "\n";
    else cout << 0 << "\n";
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

long long N, M;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    vector<int> Nums(N+1);
    vector<vector<bool>> DP(N+1, vector<bool>(N+1, false));

    for (int i = 1; i <= N; i++)
    {
        DP[i][i] = true;
        cin >> Nums[i];

        if (i > 1)
        {
            if (Nums[i] == Nums[i - 1])
            {
                DP[i - 1][i] = true;
            }
        }
    }

    for (int i = 2; i < N; i++)
    {
        int Start = 1;
        int End = Start + i;

        while (End <= N)
        {
            if (DP[Start + 1][End - 1])
            {
                if (Nums[Start] == Nums[End])
                {
                    DP[Start][End] = true;
                }
            }

            Start++;
            End++;
        }
    }


    cin >> M;

    for (int i = 0; i < M; i++)
    {
        int S, E;
        cin >> S >> E;

        if (DP[S][E]) cout << 1 << "\n";
        else cout << 0 << "\n";
    }

    return 0;
}

---