[Algorithm]Baekjoon 10942번 :: 팰린드롬?

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

10942번: 팰린드롬?

 
 
using namespace std;
 
int arr[2001] = { 0 };
int dp[2001][2001] = { 0 };
int n, m, a, b;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
 
        dp[i][i] = 1; // 1,1 도 팰린드롬이다.
    }
 
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] == arr[i + 1]) dp[i][i + 1] = 1; // 바로 오른쪽 숫자가같아도 무조건 된다.
    }
 
    cin >> m;
 
    for (int length = 2; length <= n - 1; ++length)
    {
        for (int start = 1; start + length <= n; ++start)
        {
            if (arr[start] == arr[start + length] && dp[start + 1][start + length - 1])
            {
                dp[start][start + length] = 1;
            }
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
 
        printf("%d\n", dp[a][b]);
    }
}
 
 
 
 

 

 

주어진 수열을 토대로 매번 주어지는 특정 start부터 특정지점 end까지 팰린드롬인지의 여부를 출력해야하는 문제이다.

당연히 그때그때 반복문돌려서하면 시간초과다. 시간제한이 0.5초밖에 안된다.

그래서 다음과같은 성질을 이용해서 dp테이블을 업데이트한다.

 

int dp[i][j] = 1 or 0   // 1이면 i번쨰 인덱스부터(start) j번째(end) 까지의 수열은 팰린드롬이라는 의미. 0은 아니란 뜻.

 

그렇다면 arr[i] == arr[j] (양끝이 같고), dp[i+1][j-1] == 1 (안쪽수열이 팰린드롬이면) dp[i][j] = true; (i~j도 팰린드롬이다!)

 

다른분들 코드보면 끝에서부터 하는데, 나는 직관적으로 이해하려고 처음부터 업데이트했다.

2중반복문으로, start ~ end에 이르는 길이를 정해주고 해당길이만큼 전부 업데이트 해줬다.

즉 처음에는 length가 2니까, n == 7이라 가정했을 때

(1,3) , (2,4), (3,5), (4,6), (5,7) 을 업데이트해주고, 그다음은 length가 3이니까

(1,4), (2,5), (3,6), (4,7) 을 업데이트 해주는 식이다.

 

아직은 이런문제 나오면 전혀 쉽게 풀지를 못한다..