[C++] BAEKJOON 10942 팰린드롬?

 

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

10942번: 팰린드롬?

일반적으로 팰린드롬을 판별하기 위해서는 맨 앞과 맨 뒤, 앞에서 두번째와 뒤에서 두번째 … 다음과 같이 비교해봐야 하므로 O(N) 의 시간복잡도가 걸립니다. 이 문제 같은 경우에는 질문이 M 개이므로 전체 시간복잡도는 O(MN) 이 됩니다. 이 때 M 의 범위가 1 ≤ M ≤ 1,000,000 이므로 시간초과에 걸리게 됩니다.

이를 해결하기 위해서 동적계획법 으로 접근하였습니다.

• 길이가 1 인 경우

  길이가 1인 경우에는 앞에서 읽던 뒤에서 읽던 같으므로 항상 팰린드롬이 성립합니다.

• 길이가 2 인 경우

  길이가 2인 경우에는 앞의 수와 뒤의 수가 같아야 팰린드롬이 성립합니다.

• 길이가 3 이상인 경우

  길이가 3 이상인 경우에는 동적계획법을 사용하여 맨 앞과 맨 뒤의 일치여부 와 그 둘을 제외한 나머지 부분이 팰린드롬인지 확인합니다.

#include <iostream>

using namespace std;

int number[2001];
// i 번째 수부터 j 번째 수가 팰린드롬을 이루는지 여부
int dp[2001][2001];

int main() {
    
    int N,M;
    cin >> N;


    for (int i=1;i<=N;i++){
        cin >> number[i];
    }

    // 길이가 1일 때
    for (int i=1;i<=N;i++){
        dp[i][i] = 1;
    }
    // 길이가 2일 때
    for (int i=1;i<=N-1;i++){
        if (number[i]==number[i+1]) dp[i][i+1] = 1;
    }
    // 길이가 3 이상일 때
    for (int k=3;k<=N;k++){
        for(int i=1;i<=N-k+1;i++){
            int j=i+k-1;
            if (number[i]==number[j] && dp[i+1][j-1])
                dp[i][j] = 1;
        }
    }
    cin >> M;
    for (int i=0;i<M;i++){
        int start, end;
        scanf("%d%d", &start, &end);
        printf("%d\n", dp[start][end]);
    }
    return 0;
}

일반적으로 cin, cout 을 사용해 입출력을 제어하다가 마지막 부분에서는 scanf 와 printf 를 통해 입출력을 하였습니다. M 의 값이 굉장히 크므로 많은 입출력을 필요할 때는 둘의 시간 차이 때문에 시간초과가 나는 경우가 있으므로 조심하시길 바랍니다.