[10942번] 팰린드롬?

문제 출처 : 

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

알고리즘 분석 :

팰린드롬이란? 1 2 2 1처럼 앞의 수와 뒤의 수가 같은것을 의미한다.

즉, 반으로 나누어서 거울처럼 겹쳐지는지 확인하여 겹쳐지면 팰린드롬이다.

1 3 1은 팰린드롬이지만 1 2 3 은 팰린드롬이 아니다. (1,3이 같은 수가 아니므로)

다이나믹 프로그래밍으로 풀라는 힌트가 존재하지만, 어떤 이유에서 그렇게 풀어야 되는지는 잘 모르겠다.

하지만 DP가 아니고도 단일 for문으로 해결 할 수 있기에 알고리즘의 시간 복잡도 및 공간 복잡도 면에서는 부담이 덜 되는 알고리즘이다.

소스 코드 : 

#include <stdio.h>
 
int main()
{
    int n,m, arr[2001];
    int start, end;
    int tstart, tend;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    // m == tCase
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &start, &end);
 
        // start를 1로 지정하면 배열의 처음(0)을 의미하니 tstart, tend에 각각 -1씩 해준다.
        tstart = start - 1;
        tend = end - 1;
 
        // for문의 순회는 start + end의 절반만 돌면된다. ex) 1 2 3 4면 1 2까지만 돌면 된다.
        for (int j = start; j <= (start + end) / 2; j++)
        {
            // 앞과 뒤의 수가 일치하면
            if (arr[tstart] == arr[tend])
            {
                 // 순회의 끝이라면
                if (j == (start + end) / 2)
                {
                    printf("1\n"); break;
                }
                tstart++; // tstart는 증가, tend는 감소(다음 수 계속 확인)
                tend--;
            }
 
            // 하나라도 틀리면 팰린드롬이 아니다.
            else
            {
                printf("0\n");
                break;
            }
        }
 
    }
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>