백준 10942번 : 팰린드롬?

  난 이 문제에 불만이 많다! 일단 팰린드롬이 뭔지 설명조차 제대로 안되어있다.

 

아니 어떻게 1, 2, 1은 팰린드롬이고 2, 1, 3, 1은 팰린드롬이 아니다.

라는 문장만 보고

아하 팰린드롬은 대칭인 형태를 의미하는구나! 라고 알 수 있단말인가?

 

  대칭 수열인지, 커졌다 작아지는 바이토닉한 수열인지 아니면 1, 2, 1, 2, 1, 2 이렇게 반복되는 수열인지 알게뭐람? 결국 인터넷에 검색해보고나서야 팰린드롬이 대칭인 수열을 의미한다는 사실을 알았다. 고쳐라! 백준!

 

  그리고 또 하나는 시간 제한인데... 사실 이건 뭐 내 지식 부족이긴 하지만 잘한것을 틀렸다고 하는건 화난다! 위의 이유로 화내는 김에 그냥 같이 문제에게 화낼테다. 나는 C++로 코딩할 때 scanf나 printf보다는 cin, cout을 즐겨 쓰는데 좀 더 깔끔해보이기 때문이다. 그런데 찾아보니 cin, cout은 scanf, printf보다 속도가 많이 느리다고 한다. 처음에 나는 그 사실을 모르고 인터넷에 떠도는 소스들보다 더 깔끔하게 짰는데도 시간 초과가 발생해서 매우 화가 나서 문제를 꿀밤 때려버리고 싶을 지경이였다. cin, cout은 포기를 못하니 호환을 꺼주는 ios_base :: sync_with_stdio(false);를 이용해서 시간을 줄였다.

 

---

  서론이 길었고 아무튼 알고리즘은 이렇다. 보통 길이 n인 수열이 대칭임을 판별하려면 arr[i]와 arr[n - 1 - i]가 같은지를 n/2번 체크하면 된다. 그런데 그럴 경우 중복으로 체크하는 경우가 많아지기 때문에 시간초과가 나기 마련이다. 따라서 다른 방식으로 접근을 해야한다.

 

양 끝의 숫자가 같고 양 끝을 제외한 수열이 펠린드롬이면 그 수열은 펠린드롬이다.

 

  예를 들어서 3 2 5 2 3 이라는 수열이 있을 때 양 끝의 숫자(3과 3)가 같고 양 끝을 제외한 수열 (2 5 2)가 펠린드롬이라면 그 수열(3 2 5 2 3)은 펠린드롬이라는 얘기다. 따라서 어떤 수열이 펠린드롬인지 아닌지를 체크하려면

 

1. 양 끝의 숫자가 같다.

2. 양 끝을 제외한 수열이 펠린드롬이다.

 

를 만족하는지 체크하면 된다. 그러므로 2번 조건에 의해 DP를 사용할 수 있게 된다! 다만 초기값이 필요하므로 수열의 길이가 1일 때(시작값과 끝값의 위치 gap이 0)와 수열의 길이가 2일 때(시작값과 끝값의 위치 gap이 1)는 직접 초기화를 시켜주어야 한다.

#include <iostream>

using namespace std;

int n, m;
int num[2002];
bool pelin[2002][2002];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    
    for(int gap = 0; gap < n; gap++)
    {
        for(int i = 0; i + gap < n; i++)
        {
            int start = i;
            int end = i + gap;
            
            if(gap == 0) pelin[start][end] = true;
            else if(gap == 1 && num[start] == num[end]) pelin[start][end] = true;
            else if(num[start] == num[end] && pelin[start + 1][end - 1]) pelin[start][end] = true;
            else pelin[start][end] = false;
        }
    }
    
    cin >> m;
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        
        cout << pelin[a-1][b-1] << "\n";
    }
 
    return 0;
}