[DynamicPrograming]BAEKJOON10942 - 팰린드롬?

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

백준 문제 특유의 거지같은 빡센 시간제한과 용량제한이 있는 문제이다.

이렇게 시간이 극단적으로 적을 때는 c++에서 cin, cout을 사용하면 시간이 모자라게 된다.

다행히도 vector를 배열로 써야하거나 그런 상황까지는 오지 않는다.

어쨋든 위의 조건때문에 틀렸다면 cin,cout을 printf와 scanf로 바꾸면 아주 쉽게 통과할 것이다.

 

질문 M개의 갯수의 제한이 백만개나 되기 때문에 0.5초는 매우 빡빡하다.

따라서 질문을 저장해놓고 쓴다던지(vector나 배열) 질문의 입출력이 cin, cout을 사용한다면 이미 그것만으로 시간은 넘친다.

 

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

 

일단 팬린드롬이 뭔지부터 알아야한다.

팰린드롬이란 대칭성을 이루는 문자열을 의미한다. 이를 한국말로는 회문이라한다.

이를 검사하는 것이다.

 

1 2 1 3 1 2 1

 

가령 위와 같은 회문은 팰린드롬이다.

다만 문제이서 묻는 것은 부분부분 봤을때도 회문이냐?

즉 부분집합도 팰린드롬을 이루는가이다.

 

먼저 시간,공간을 무시하고 팰린드롬을 풀어보자.

특정 문자열이 팰린드롬인지 아는 방법은 시작을 s라 잡고 끝을 e라잡았을때 동시에 시작과 끝을 비교하고 한칸씩 서로 땡긴다.

 

#1. (1) 2 1 3 1 2 (1)
#2. 1 (2) 1 3 1 (2) 1
#3. 1 2 (1) 3 (1) 2 1
#4. 1 2 1 ((3)) 1 2 1

이 동작은 특정 문장의 길이를 n이라 가정할 때 O(n/2)의 시간복잡도, 즉 O(n)이 걸리게된다.

이러한 작업을 모든 경우의 수를 따진다면 총 n*n의 경우의 수가 있다. 즉 모든 작업의 수는 O(n^2)이 된다.

그러면 O(n)*O(n^2)이므로 O(n^3)이라는 미친 시간복잡도가 걸리게된다.

 

시간을 줄이는 방법은 크게 보면 greedy와 dp가 존재한다.

하지만 해당방법은 아무리 봐도 greedy는 힘들 것 같다. 추가적인 조건이 걸려있지 않기 때문이다.

그렇다면 dp로 푸는수 밖에 없다.

 

하지만 dp로 풀이방법이 쉬이 떠오르지 않을 수 있다.

일반적인 재귀의 진행방식과 조금 차이가 있다.

팰린드롬을 분할정복하려면 어떻게 해야할까??

#1. (1) 2 1 3 1 2 (1) -> 2 1 3 1 2가 팰린드롬이면 양 끝만 비교하면된다.
#2. 1 (2) 1 3 1 (2) 1 -> 1 3 1이 팰린드롬이면 양 끝만 비교하면된다.
#3. 1 2 (1) 3 (1) 2 1 -> 3이 팰린드롬이면 양 끝만 비교하면된다.
#4. 1 2 1 ((3)) 1 2 1 -> 1자릿숫자는 무조건 팰린드롬이다.

사실 우리가 진행했던 방식에 힌트가 있다.

특정 회문을 level별로 생각해보자. 가령위를 예로 들자면

1레벨상황에서 2레벨 상황의 값을 안다면 서로 양쪽만 비교하면 된다.

2레벨 상황에서도 3레벨 상황의 값을 안다면 서로 양쪽만 비교하면 된다.

4레벨 상황에서는 한자리이므로 무조건 팰린드롬이다.

 

이 방식을 생각해보면 재귀의 진행방향을 알 수 있다.

먼저 시작점 s와 종착점 e의 거리가 d라고 가정하자. d가 0이라면, 무조건 펠린드롬이다.

비교도 할 필요없다. 즉 s==e라면 무조건 팰린드롬이다.

그럼 d가 1이라면 어떻게 될까? 이 경우는 s와 e의 값을 비교하면된다. 둘이 동등하면 팰린드롬이다.

그 이상이라면?

 

1.양 끝값이 동등하며
2.양 끝값을 제외한 그 사이 까지의 값이 팰린드롬이라면
3.팰린드롬이다.

 

이제 분할정복을 할 수 있다.

그냥 돌리면 중복된 수많은 경우의 수가 생기며 따라서 나머지는 메모이제이션을 해주면 된다.

dp를 적용할 경우 시간복잡도는 O(n^2) + O(m)이 되는데 n은 2,000이고 m은 1,000,000 결국 O(n^2)라 봐도 무방하다.

대신 공간 복잡도가 O(n^2)로 늘어나게된다. 기존에는 O(n)이였다.

다만 문제의 조건이 256mb이며 n^2의 상한선이 4,000,000이므로 용량은 아주 충분하다.

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> ARR;
int tmp;
int ts, te;

vector<vector<int>> memo;

int main() {

    //init
    {
        scanf("%d", &N);
        ARR.push_back(0);
        for (int n = 1; n <= N; n++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
        scanf("%d", &M);
        memo.resize(N + 1, vector<int>(N + 1, -1));
    }

    for (int d = 0; d < N; d++) {
        for (int s = 1; s <= N - d; s++) {
            if (d == 0) {
                memo[s][s] = 1;
            } else if (d == 1) {
                memo[s][s + d] = ARR[s] == ARR[s + d];
            } else {
                memo[s][s + d] = memo[s + 1][s + d - 1] ? ARR[s] == ARR[s + d] : 0;
            }
        }
    }

    for (int m = 1; m <= M; m++) {
        scanf("%d %d", &ts, &te);
        printf("%d\n", memo[ts][te]);
    }

    return 0;
}

위의 코드는 for문을 사용한 코드이다.

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> ARR;
int tmp;
vector<vector<int>> memo;


int func(int s, int e) {
    if (s == e) {
        memo[s][e] = 1;
        return 1;
    } else if (s + 1 == e) {
        return memo[s][e] = ARR[s] == ARR[e];
    } else {
        if (memo[s + 1][e - 1] == -1) {
            memo[s + 1][e - 1] = func(s + 1, e - 1);
        }
        return memo[s][e] = memo[s + 1][e - 1] ? ARR[s] == ARR[e] : 0;
    }
}

int main() {

    //init
    {
        scanf("%d", &N);
        ARR.push_back(0);
        for (int n = 1; n <= N; n++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
        scanf("%d", &M);
        memo.resize(N + 1, vector<int>(N + 1, -1));
    }

    int ts, te;

    for (int m = 1; m <= M; m++) {
        scanf("%d %d", &ts, &te);
        if (memo[ts][te] == -1) {
            memo[ts][te] = func(ts, te);
        }
        printf("%d\n", memo[ts][te]);
    }

    return 0;
}

해당 코드는 재귀로 구현한 코드이다.