[BOJ] 백준 17144 팰린드롬? c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/10942 

10942번: 팰린드롬?

---

풀이

입력한 구간이 팰린드롬인지 확인하는 문제이다! 시간 제한에서 dp로 풀어야 한다는 것을 알았다.

어떻게 하면 dp로 풀 수 있을까?

먼저 dp 배열을 하나 선언한다. (기본 false)

bool dp[2001][2001];

해당 배열에서 dp[i][j]는 i번째 수부터 j번째 까지 팰린드롬인지 여부를 나타난다.

S, E가 같은 경우 ex) 1

이 경우는 팰린드롬이다! => 따라서 dp[i][i]는 true이다.

 

S, S+1가 같은 경우 ex) 1 1

1 1, 2 2 등 길이가 2일때 이전 수와 전 수가 같으면 팰린드롬이다.

위의 S, E 가 같은 경우와 한번에 처리하면 아래와 같다.

for(int i = 1; i <= N-1; i++){
    dp[i][i] = true;
    if(v[i] == v[i+1])
        dp[i][i+1] = true;
}
dp[N][N] = true;

dp[S][E]가 true이면 dp[S+1][E-1]도 true이다.

1 2 3 2 1 이 있다고 해보자. 이 경우 팰린드롬이다.

이때 2 3 2도 팰린드롬이다.

따라서 인덱스를 순회할 i, j를 선언 후 조건을 적용하면 아래와 같다.

for(int i = N - 1; i >= 1; i--){
    for(int j = i + 1; j <= N; j++){
        if(v[i] == v[j] && dp[i+1][j-1])
            dp[i][j] = true;
    }
}

---

코드

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

using namespace std;

int N, M;
bool dp[2001][2001];

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    vector<int> v(N+1);
    for(int i = 1; i <= N; i++)  
        cin >> v[i];

    for(int i = 1; i <= N-1; i++){
        dp[i][i] = true;
        if(v[i] == v[i+1])
            dp[i][i+1] = true;
    }
    dp[N][N] = true;

    for(int i = N - 1; i >= 1; i--){
        for(int j = i + 1; j <= N; j++){
            if(v[i] == v[j] && dp[i+1][j-1])
                dp[i][j] = true;
        }
    }

    cin >> M;
    for(int i = 0; i < M; i++){
        int S, E;
        cin >> S >> E;
        cout << dp[S][E] << '\n';
    }

    return 0;
}