[백준] 10942번*

💻 C++ 기반

팰린드롬?
https://www.acmicpc.net/problem/10942

✔️ 팰린드롬: 거꾸로 읽어도 같은 문장, 낱말, 숫자, 문자열인 것
✔️ 주어지는 N개의 자연수는 한 자리 수만 오는 것이 아니라 100,000 자리 수까지 올 수 있음
✔️ 331, 121, 133은 팰린드롬이 아님 (∵ 133, 121, 331과 다르기 때문)
✔️ 1, 11, 111은 팰린드롬이 아님 (∵ 111, 11, 1과 다르기 때문)

1. 테이블 정의하기
dp[i][j]: i번째 수부터 j번째 수까지 팰린드롬을 이루는지/아닌지

2. 점화식 찾기
이미 팰린드롬인 수열의 양끝에 같은 숫자가 오면 또 팰린드롬이다.

i번째 수와 j번째 수가 같은 숫자인지 확인 후,
dp[i + 1][j - 1]이 1이면 dp[i][j]도 1이다.

⚠️ 이때, i와 j의 차이가 1, 2, 3, … 이런 식으로 증가해나가면서 dp 배열을 채워줘야 함 ( 단순히 행 -> 열 순으로 dp 배열 채워주면 1이 들어가야 할 자리에 0이 들어가버림)

3. 초기값 정하기
한 자리 수열은 모두 다 팰린드롬이므로,
dp[1][1], dp[2][2], dp[3][3], … 을 1로 초기화해준다.

#include <cstdio>

#define MAX 2001

using namespace std;

int numbers[MAX];
int dp[MAX][MAX];

int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &numbers[i]);
    }

    for (int i = 1; i <= N; i++)
    {
        dp[i][i] = 1;
    }
    for (int diff = 1; diff < N; diff++)
    {
        for (int i = 1; i + diff <= N; i++)
        {
            if (numbers[i] == numbers[i + diff])
            {
                if (diff == 1)
                {
                	// 두 자리수 예외처리
                    dp[i][i + diff] = 1;
                }
                else
                {
                    dp[i][i + diff] = dp[i + 1][i + diff - 1];
                }
            }
        }
    }

    int M;
    scanf("%d", &M);
    while (M--)
    {
        int S, E;
        scanf("%d %d", &S, &E);
        printf("%d\n", dp[S][E]);
    }
    return 0;
}