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

문제 링크

https://www.acmicpc.net/problem/15686

---

 

◆문제 해결 및 설명◆

문제 : 수열을 주고, 어디 부터 어디까지가 펠린드롬 이냐 묻는 질문에 대답하는 문제

 

펠린드롬이란 거꾸로 읽어도 똑같은 문장이나 단어를 뜻한다. 

따라서 직접 뒤집어서 비교하거나, 포인터를 통해서 문자가 같은지 판별해주면 되는데 이 문제는 수열의 크기 최대 2,000, 질문의 개수 최대 1,000,000 이며 시간 제한이 0.5초 이다.

위에서 이야기한 두 방법으로는 풀 수 가 없다.

 

다이나믹 프로그래밍으로 풀 수 있는데

기준을 잡고 기준이 펠린드롬일 때, 좌우로 하나씩 증가 했을 때 좌우가 같은 문자열이라면 그 문자는 펠린드롬이다.

abcba에서 c가 기준인것이 보일 것이다. 좌우로 하나 늘린 bcb도 펠린드롬, abcba도 펠린드롬이다.abcda의 경우 c는 펠린드롬 bcd는 펠린드롬이 아니고, 이후에 증가하는 모든 경우에도 펠린드롬이 아니다.(c가 기준일 때)이를 활용하여 문제를 풀 수 있다.

 

나의 경우에는 행을 시작위치, 열을 끝나는 위치로 하는 이차원 배열 선언하였고, 펠린드롬 일때 1로 배열에 저장하였다.전의 값이 펠린드롬인지 확인하기 위해서 이차원배열[i + 1][k - 1] 값이 양수인지 검사하고 행과열의 문자열이 같은지 확인하였다.

 

◆코드 전문◆

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int N_size, Q_size, answer;

    cin >> N_size;
    vector<int> array(N_size);
    for (int i = 0; i < array.size(); i++)
    {
        int buf;
        cin >> buf;
        array[i] = buf;
    }

    cin >> Q_size;
    vector<pair<int, int>> questions(Q_size);
    for (int i = 0; i < questions.size(); i++)
    {
        int startBuf, endBuf;
        cin >> startBuf >> endBuf;
        questions[i] = make_pair(startBuf, endBuf);
    }

    vector<vector<int>> matirxArray(N_size, vector<int>(N_size));
    for (int i = matirxArray.size() - 1; i >= 0; i--)
    {
        for (int k = i; k < matirxArray[i].size(); k++)
        {
            if (array[i] == array[k])
            {
                matirxArray[i][k] = 1;
                if (i + 1 >= matirxArray.size() || k - 1 < 0)
                {
                    continue;
                }
                if (k - 1 < i + 1)
                {
                    continue;
                }
                if (matirxArray[i + 1][k - 1] <= 0)
                {
                    matirxArray[i][k] = 0;
                }
            }
        }
    }

    for (int i = 0; i < questions.size(); i++)
    {
        cout << matirxArray[questions[i].first - 1][questions[i].second - 1] << "\n";
    }
}