10942. 팰린드롬?

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

10942번: 팰린드롬?

 

풀이

필요 알고리즘: 다이나믹 프로그래밍(DP)

 

N, M의 값의 범위에 비해 시간 제한이 0.5초로 빡빡하므로 주어진 질문마다 팰린드롬을 그때그때 확인하는 방법은 거의 불가능하다. 그러므로 DP를 활용해 S번째 수부터 E번째 수까지가 팰린드롬인지를 전부 저장한 뒤, 질문에 따라 해당하는 답을 내놓는다면 TLE에 걸리지 않고 통과할 수 있다.

 

그렇다면 DP로 팰린드롬인지를 어떻게 판별하는지 알아보자. 일단 2차원 배열 dp를 선언하자. dp[S][E]는 S번째 수부터 E번째 수까지가 팰린드롬이면 true, 아니면 false를 저장한다고 정의한다.

 

그리고 배열 dp의 값을 채워나간다. 예제의 수열 1 2 1 3 1 2 1을 기준으로 하고, dp[1][1]부터 하나씩 채워나가 보자.

 

먼저, 수열의 첫 번째 수 1을 받고, dp[1][1]이 팰린드롬인지를 저장한다. 수가 단 하나일 경우는 무조건 팰린드롬이므로 dp[1][1] = true이다.

S \ E	dp[S][1]	dp[S][2]	dp[S][3]	dp[S][4]	dp[S][5]
dp[1]	true

다음으로 수열의 두 번째 수 2를 받고, dp[1][2]와 dp[2][2]가 팰린드롬인지를 저장한다. 수가 두 개일 경우에는 두 수가 전부 같아야 팰린드롬이다(ex: 1 1, 3 3). 그러나 1 2는 팰린드롬이 아니므로 dp[1][2] = false이다. dp[2][2]는 dp[1][1]과 마찬가지 이유로 true가 된다.

S \ E	dp[S][1]	dp[S][2]	dp[S][3]	dp[S][4]	dp[S][5]
dp[1]	true	false
dp[2]		true

수열의 세 번째 수 1을 받고, dp[1][3] ~ dp[3][3]이 팰린드롬인지를 저장한다. 수가 세 개 이상일 경우에는, 첫 번째 숫자와 마지막 숫자가 같고, 그 사이의 숫자들이 팰린드롬이면 전체가 팰린드롬이 된다(ex: 2 3 3 2, 5 4 1 4 5). 즉, (수열의 첫 번째 수) == (수열의 마지막 수) && dp[S + 1][E - 1]이면 dp[S][E]는 팰린드롬이다. 실제로 수열 1 2 1은 첫 번째와 마지막 숫자가 같고, 그 사이의 수열 2에 해당하는 dp[2][2] = true이므로 dp[1][3] = true가 된다. dp[2][3]과 dp[3][3]은 위에서 설명했던 대로 각각 false, true이다.

S \ E	dp[S][1]	dp[S][2]	dp[S][3]	dp[S][4]	dp[S][5]
dp[1]	true	false	true
dp[2]		true	false
dp[3]			true

 

이런 식으로 dp[5][5]까지 채워나가면 다음과 같다.

dp[1][4](1 2 1 3): 1 != 3 && dp[2][3] = false

dp[2][4](2 1 3): 2 != 3 && dp[3][3] = false

dp[3][4](1 3): 1 != 3 = false

dp[4][4](3): true

 

dp[1][5](1 2 1 3 1): 1 == 1 && dp[2][4] = false

dp[2][5](2 1 3 1): 2 != 1 && dp[3][4] = false

dp[3][5](1 3 1): 1 == 1 && dp[4][4] = true

dp[4][5](3 1): 3 != 1 = false

dp[5][5](1): true

S \ E	dp[S][1]	dp[S][2]	dp[S][3]	dp[S][4]	dp[S][5]
dp[1]	true	false	true	false	false
dp[2]		true	false	false	false
dp[3]			true	false	true
dp[4]				true	false
dp[5]					true

 

이렇게 범위에 따른 팰린드롬 여부를 저장한 뒤, S와 E가 주어지면 그에 맞는 대답을 배열에서 찾아 출력하면 된다.

 

시간 복잡도

1부터 \(N\)까지의 합, 즉 \(\frac{1}{2}N(N+1)\)만큼의 연산을 하므로 시간 복잡도는 \(O(N^{2})\)이다.

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int N, M, S, E;
int arr[2001];
// dp[i][j]: i번째 수부터 j번째 수가 팰린드롬이면 true, 아니면 false
vector<vector<bool>> dp(2001, vector<bool>(2001, false));

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
        
        for(int j = 1; j <= i; j++) {
            if(i - j == 0) dp[j][i] = true;
            else if(i - j == 1) dp[j][i] = (arr[j] == arr[i]);
            else dp[j][i] = (arr[j] == arr[i]) && dp[j + 1][i - 1];
        }
    }
    
    cin >> M;
    while(M--) {
        cin >> S >> E;
        cout << dp[S][E] << '\n';
    }
    
    return 0;
}

배열 dp를 vector 컨테이너를 이용하여 선언하였는데, 이렇게 하면 bool형 배열을 선언하는 것보다 사용 메모리를 줄일 수 있다. bool형 배열은 한 칸의 크기가 1byte지만, bool형 vector 컨테이너는 1bit이기 때문이다.