백준 No.10942 [팰린드롬?]

Baekjoon Online Judge No.10942 [팰린드롬?]

---

   Problem   

10942번: 팰린드롬?

---

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
typedef pair<int, int> PII;
 
int N, M; // max(N) == 2,000
vector<int> nums;
vector<vector<bool>> dp;
vector<bool> ans;
 
void Memoization() { // O(4,000,000)
    if (nums[0] == nums[1]) dp[0][1] = true;
    if (nums[0] == nums[2]) dp[0][2] = true;
    if (nums[N - 3] == nums[N - 1]) dp[N - 3][N - 1] = true;
    if (nums[N - 2] == nums[N - 1]) dp[N - 2][N - 1] = true;
 
    for (int j = 1; j <= 2; j++) {
        for (int i = 1; i < N - 1 - j; i++) {
            int I = i;
            int J = i + j;
 
            if (nums[I] != nums[J]) continue;
            else {
                dp[I][J] = true;
 
                int curI = I;
                int curJ = J;
 
                while (curI--) {
                    if (++curJ == N) break;
 
                    if (nums[curI] == nums[curJ])
                        dp[curI][curJ] = true;
                    else break;
                }
            }
        }
    }
} // dp[i][j] == nums[i] 부터 nums[j] 까지가 펠린드롬인지
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
    nums.resize(N);
    dp.assign(N, vector<bool>(N, false));
 
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
        dp[i][i] = true;
    }
 
    Memoization();
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        PII prob;
        cin >> prob.first >> prob.second;
 
        int S = prob.first - 1;
        int E = prob.second - 1;
 
        ans.push_back(dp[S][E]);
    }
 
    for (auto elem : ans) cout << elem << '\n';
}

---

   Algorithm   

  2D 방식으로 memoization을 진행했다. 아래 그림을 보자.

 

규칙 ( 각 옅은회색 칸들은 dp[ i ][ j ] )

  먼저, 파란 칸들은 i 와 j 의 값이 같을때의 경우이므로, 모두 팰린드롬 숫자이다.

 

• dp[ k ][ k ] == 1 ( 0 <= k < N )

  dp[ i ][ j ] 가 팰린드롬 수가 되기위한 조건을 두 개라고 생각하였다.

 

1. dp[ i + 1][ j - 1 ] 가 true일 때. 즉, nums[ i + 1 ] 부터 nums[ j - 1 ] 까지의 수열이 팰린드롬일때.
2. nums[ i ]와 nums[ j ] 가 같을때. 즉, 처음과 끝이 같을 때.

  위 두 조건을 만족한다면 dp[ i ][ j ]는 팰린드롬이다. 아래 그림을 참고하면 된다.

dp[ i ][ j ] 가 true 일 조건 예시

  위 예시 그림은 dp[0][5]를 구하는 예시이다. 양 끝의 숫자인 nums[0]과 nums[5]가 같고 이 두 숫자를 뺀 가운데의 숫자들이 팰린드롬을 이루니 (dp[1][4] == true) dp[0][1]는 팰린드롬 이므로 true값을 가진다.

 

  따라서 이 두 조건을 점화식에서 사용하였다. (#24 ~ #37 line)

 

1. dp[ i + 1][ j - 1] == true
2. nums[ i ] == nums[ j ]

  위 조건의 첫 번째 조건을 사용하기 위해선 또한 선제조건이 있다. 참고하고자 하는 dp[ i + 1 ][ j - 1 ]의 값이 유효해야한다. 아래와 같이 정리해보았다.

 

1. i + 1, j - 1 은 0 이상 N 미만의 숫자를 가져야 함
2. i + 1 == j - 1 라면 dp의 값은 항상 1이므로 딱히 의미가 없다.

  memoziation을 위해 탐색하는 과정이 위 규칙 그림의 검은색 화살표처럼 탐색 하였으니 우선 첫 번째 선제조건은 고려할 필요가 없다. 그리고 두 번째 조건을 위해 위 dp[ k ][ k ]는 모두 1로 초기화 시켜놓고 안 건드렸다.

 

  위 규칙 그림의 빨간색 테두리 된 부분들을 탐색하였다. dp[ i + 1 ][ j - 1 ] 값이 true인 것이 dp[ i ][ j ]가 true가 되기 위한 첫 번째 조건인데 이는 직관적으로 보면 위 규칙 그림의 초록, 노랑, 주황 화살표들과 같다. 좌하향대각에 위치한 dp값이 true이고, 구하고자하는 dp의 양 끝 숫자가 같으면 현재 dp값도 true가 되는 것이다. 위 규칙의 그림처럼 초록, 노랑, 주황의 방향으로 연쇄 작용을 한다. 쉽게 설명하면 음.. 양 끝 nums가 같다는 조건을 일단 무시하고 설명하면

 

• dp값이 true -> 우상향 대각 dp값이 true -> 우상향 대각 dp값이 true ->...
• 이 true chain 이 끝날 조건은 양 끝 nums가 다를 때 이다.

이에 해당하는 코드는 위 코드의 #23 ~ #35와 같다.

 

  빨간 테두리 안에 있어도 저러한 방식으로 할 필요가 없는 index가 4칸이 있다. 위 규칙 그림의 분홍색 부분들이다. 우상향대각칸이 존재하지 않으므로! 얘네는 #13 ~ #16 line 에서 따로 초기화를 해 주었다. 그래서 위 규칙 그림을 보면 탐색하는 순서를 나타내는 검은색 화살표는 분홍색 부분을 포함하지 않고 있다.

 

  dp vector 의 default value 를 false 로 놓고, #23 ~ #35에서 우상향 대각으로 계속해서 팰린드롬 조건을 만족하면 true로 바꾸어 준다. (#24 ~ #36 line) 그리고 팰린드롬 조건을 만족하지 않으면 그 이후 우상향 대각들도 모두 팰린드롬 조건을 만족하지 않을 것 이므로 #23 line 처럼 continue; 를 해준다.

 

  #43, #44 line 에 있는 것들을 처음에는 선언하지 않았었다. 그랬더니 시간초과가 났고, 저 것들을 써주니까 시간초과가 나지 않았다. #43, #44에 대해서는 그냥 C에서 사용하는 것들을 사용하지 못하게 되고 cin, cout 의 처리속도가 빨라진다 정도만 알고있었는데 더 공부를 해야할 것 같다.

---

   시행착오   

  처음에 생각한 방식은 저 방식과는 달랐다. 아래와 같이 접근했다.

dp[ i ][ j ]

  우선 dp[ k ][ k ] 는 모두 true로 초기화 하였고, dp[ k ][ k + 1 ] 는 nums[ k ] == nums[ k + 1 ] 를 만족하면 true, 아니면 false 로 초기화 하였다.

 

  그 후에 dp[ i ][ j ]가 true 일 조건은 다음과 같다.

 

1. dp[ i + 1][ j - 1] == true
2. nums[ i ] == nums[ j ]

위 그림에 파랑색과 갈색 칸을 구하기 위해서 참고되는 값들이 동일한 색상의 화살표로 직관적으로 나타나있다.

 

  탐색 순서는 빨간색 화살표 순서이다. 하지만 이 방식으로 할 경우 O(N*N/2) 의 시간복잡도를 가지므로 한번 위 실제 제출한 코드처럼 짜 본 것이다.