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

문제

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

먼저, 홍준이는 자연수 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 (1 ≤ N ≤ 2,000)이 주어진다.

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

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

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

출력

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

 

문제 풀이

전형적인 DP문제입니다.
해당 구간내에서 매번 연산을 하기에는 너무나 큰 범위이기에, 우리는 메모이제이션 방식을 사용해서 쓸데없는 연산을 줄여야 합니다.
해당 문제에서도, DP와 투포인터 알고리즘을 같이 사용해서 해결했습니다.

입력된 구간을 start와 end로 지정해서 탐색을 시작합니다.

 

테스트 케이스를 예로 들어서 설명해 보겠습니다.

1, 2, 1, 3, 1, 2, 1

1) S =1 , E = 3 [1,2,1]

1과 3을 비교합니다.

비교하면 1과1은 같은 걸로 알 수 있습니다.

그러면 이제 한칸씩 전진해서 탐색을 시작합니다.

그럼 S=2, E=2가 되고 

2와 2를 비교하므로, 1부터 3까지의 배열은 팰린드롬인 것을 알 수 있습니다.

그럼 우리는 여기서 DP값을 항상 업데이트해서 DP[2][2], DP [1][3]은 팰린드롬이라는 것을 저장합니다.

이렇게 계속 값을 저장해서, 메모이제이션 방식을 이용해서 꺼내 쓸 예정입니다.

 

2) S = 2, E = 5 [2,1,3,1]

2와 1을 비교하고, 다르니까 DP[2][5]는 팰린드롬이 아니라고 저장해 둡니다.

이렇게 계속해서 탐색범위를 좁히다가 DP값을 검사합니다. 해당 DP값이 만약 1이라면, 팰린드롬이므로, 탐색을 계속해서 진행합니다.

하지만 DP값이 0이라면, 팰린드롬이 아니라는 뜻이므로, 검사를 즉시 중단합니다.

이렇게 되면 쓸데없는 탐색을 줄일 수 있습니다.

 

요약

• DP[i][j] 는 i~j까지의 수열이 팰린드롬인지 아닌지를 나타냅니다.
• -1로 초기화하고, -1이 아니라면 메모이제이션을 실행합니다.
• start와 end의 숫자가 다르다면, 0으로 초기화하고 그 즉시 탐색중단
• 숫자가 같다면 1로 초기화하고, 다음 범위를 탐색합니다.
  • 여기서 1로 초기화하지만, 다음 범위가 팰린드롬이 아니라면 기존 탐색의 값도 0으로 바꿔줍니다.

 

 

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int>ary;
vector<vector<int> >dp;
bool funct(int start,int end);
int main(){
    cin.tie(NULL);
    ios_base :: sync_with_stdio(false);
    cin>>n;
    ary.resize(n+1,0);
    dp.resize(n+1,vector<int>(n+1,-1));
    for(int i=1; i<=n; i++){
        cin>>ary[i];
    }
    cin>>m;
    int s,e;
    for(int i=0; i<m;i++){
        cin>>s>>e;
        cout<<funct(s,e)<<"\n";
    }
}
bool funct(int start,int end){
    if(dp[start][end]!=-1){ //-1이 아니면 한번 계산을 마친 결과니까 그거 그대로 반환 -> 메모이제이션
        return dp[start][end];
    }
    if(ary[start]!=ary[end]){ //다르면 그 때의 start~end는 펠린드롬이 아님.
        dp[start][end]=0;
        return dp[start][end];
    }
    else{ //같을 경우
        dp[start][end]=1;  //start와 end가 숫자가 같으므로, 1로 선언해주고, 계속해서 탐색한 값을 업데이트 해준다.
        if(start+1<=end-1) //start가 end와 교차되서는 안된다.
        {
            dp[start][end]=dp[start][end]&&funct(start+1,end-1); //깎아서 검사.
        }
        return dp[start][end];
    }
}

 

 느낀 점

• 문제가 직관적인 편이어서, 이해하기 쉬웠고, 문제도 깔끔했다.
• 메모이제이션에 대해서 잘 모른다면, 이 문제를 통해서 개념을 알아갈수 있을것이다!