10942_팰린드롬?

10942 팰린드롬?

Concept & Idea

팰린드롬을 다이나믹 프로그래밍을 이용하여 푸는 문제였다. 또한 제한시간이 0.5초로 엄청 빡센 문제였다.
팰린드롬 체크를 단순히 떠오르는 방법으로 하게되면, 양쪽에서 체크하는 N^2만큼의 시간복잡도를 가진다.
그럼 이 문제를 다이나믹 프로그래밍을 이용하여 푸는 법은 무엇일까?

다이나믹 프로그래밍에서 가장 중요한 개념은 메모제이션이다. 또한 메모제이션을 어떻게 할 지 n에 대한 일반식으로 나타내는 것이 중요한 것 같다.
팰린드롬을 이전의 기록을 이용하여 체크할 때, ‘XXX라는 문자열이 팰린드롬이다’ && ‘_XXX_좌우에 붙는 문자들이 같다’ 라면 이 문자열 역시 팰린드롬이 된다.

이 Idea를 이용하여 다음 순서를 생각할 수 있다.

1. 길이가 1인 문자열은 무조건 팰린드롬이다.
2. 길이가 2인 문자열일 경우, 두 문자열이 동일하면 팰린드롬이다.
3. XXX라는 문자열이 팰린드롬이고 해당 문자열 좌우에 새로운 문자들이 동일하면 팰린드롬이다.

참고로 DP[i][j]배열은 i부터 j까지 팰린드롬이라고 메모제이션 해놓은 배열이다.

또한 이 문제의 정답율이 낮은 이유는 입력과 출력시간이 cout과 cin을 이용하면 오래걸리기 때문이다.
필자는 scanf와 printf를 이용하여 풀었지만, Advice를 보면 cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 사용해서 해결할 수 있다.
근데 친구말을 들어보면, 그래도 scanf와 printf가 더 빠르다는데 잘 모르겠다.

Code

#include <iostream>
using namespace std;
int n;
int arr[2001];
int m;
int dp[2501][2501];
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) {
        scanf("%d", &arr[i]);
    }
    for(int i=1; i<=n; i++) {
        dp[i][i]=1;
        if(arr[i]==arr[i+1]) {
            dp[i][i+1]=1;
            dp[i+1][i]=1;
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(dp[i][j]==0 && arr[i]==arr[j] && dp[i-1][j+1]) {
                dp[i][j]=1;
                dp[j][i]=1;
            }
        }
    }
    cin>>m;
    for(int i=0; i<m; i++) {
        int a,b;
        scanf("%d %d", &a, &b);
        printf("%d\n",dp[a][b]);
    }

}

 

Fealing

사실 이 문제의 경우, 대각선을 기준으로 대칭을 이루기 때문에 굳이 N^2번 체크할 필요가 없다. (N^2)/2번 체크를 함으로써 시간을 단축시킬 수 있을 것 같다.
‘틀렸습니다’를 두려워 하지말고, 효율적인 코드를 짜는 연습을 해야한다.