[백준/C++] 알고리즘 10942번 - 팰린드롬?

 

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 10942번을 풀어보도록 하겠습니다.

 

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

 

[문제 접근]

시간 제한은 0.5초

M의 크기는 1백만, N의 크기는 2천입니다.

여기서 완전탐색으로 질문 1번에 수열을 모두 탐색을 하면 n번 연산이 필요하기 때문에 총 연산량은 M x N 으로 20억연산이 됩니다.

c++에서 1초에 대략 1억번 연산을 한다고 했을 때, 20초로 시간 초과가 납니다.

즉 이 문제는 O(N)의 시간복잡도를 가진 알고리즘으로 접근해야 하고, 다이나믹 프로그래밍이 적합하다는 것을 유추할 수 있습니다.

 O(NlogN)시간복잡도를 가진 알고리즘을 생각할 수 있지만, 팰린드롬의 반복성을 생각했을 때 다이나믹프로그래밍+ O(N)이 더 가능성이 높습니다)

이 문제가 다이나믹프로그래밍으로 풀어야 한다는 것은 어느정도 납득이 되었습니다.

근데 이제 여기서부터가 막막하더라구여. 패턴을 어떻게 찾아내야 하지?

저는 패턴을 찾기 위해 문제의 예시를 살펴보면서 알고리즘 설계의 기준과 패턴을 찾으려고 시도했습니다.

아래는 제가 실제로 문제풀면서 끄적인 낙서인데,  정리하면

예시로 이해 및 분석 -> 중앙값이 기준임을 파악 -> S번째부터 E번째가지의 개수가 홀수인 것만 고려 ->  dp[i][j]: 중앙이 i번째인 질문에서 j거리만큼 떨어져있는 s,e가 팰린드롬인지 아닌지 여부 -> 짝수인 것도 있다는 것 발견 -> '규칙성 못찾겠다 선포 푸념' -> S번째부터 E번째가지의 개수가 홀수인 거랑 짝수인 거랑 큰 차이가 없다는 것을 발견

 

[풀이 전략]

1. dp[i][j]는 중앙이 i번째 수이면서, 중앙으로부터 j거리 떨어진 부분 수열의 팰린드롬 여부( 단, 부분 수열의 개수가 홀수)

2. dpeven[i][j]는 1번과 동일한 정의이나 부분 수열의 개수가 짝수인 경우.

3. dp[i][j] 초기화

- dp[i][0]은 무조건 1로 초기화

- arr[i-j] == arr[i+j]이고, dp[i][j-1]이 1인 경우만 dp[i][j] = 1 

4. dpeven[i][j] 초기화

- arr[i] == arr[i+1]인 경우만 dpeven[i][0] = 1 초기화

- arr[i-j] == arr[i+j+1]이고, dpeven[i][j-1] = 1인 경우만, dpeven[i][j] = 1

5. dp와 dpeven을 이용하여 질문에 대한 답 구하기.

 

[코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;

int n,m;

int arr[2001];
int dp[2001][2001]; // 홀수
int dpeven[2001][2001]; // 짝수
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;

    // 수열 초기화
    for(int i = 1 ; i <= n ; i++) cin >> arr[i];

    // s번째수부터 e번째수까지의 개수가 홀수인 경우
    for(int i = 1 ; i <= n ; i++){
        dp[i][0] = 1;
        for(int j = 1 ; j < i ; j++) {
            if(arr[i-j] != arr[i+j]) continue;
            if(dp[i][j-1] == 0) continue;
            dp[i][j] = 1 ;  
        }
    }

    // s번째수부터 e번째수까지의 개수가 짝수인 경우
    for(int i = 1 ; i <= n ; i++){
        if(arr[i] == arr[i+1]) {
            dpeven[i][0] = 1;
        }
        for(int j = 1 ; j < i ; j++) {
            if(i+j+1 > n) continue;
            if(arr[i-j] != arr[i+j+1]) continue;
            if(dpeven[i][j-1] == 0) continue;
            dpeven[i][j] = 1 ;  
        }
    }

    cin >> m ;
    for(int i = 0 ; i < m ; i++){
        int s,e ;
        cin >> s >> e ;
        if((e-s) % 2 == 0) {
            cout << dp[(e+s)/2][(e-s)/2]<<'\n';
        } else {
             cout << dpeven[(e+s)/2][(e-s)/2]<<'\n';
        }
    }
    
}

 

[배울 점]

- 다이나믹 프로그래밍은 패턴을 찾아야 합니다. 여기서 패턴은 반복되는 상황을 의미합니다. 현재상황과 이전상황사이의 패턴, 큰 문제를 쪼갠 작은 문제가 같은 패턴인 상황 등.