팰린드롬?

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

문제 설명이 조금 부족한데, 숫자 하나를 문자 하나로 취급해야 한다.

여튼 노말하게 DP를 써주면 풀리는 문제이다.

아래와 같이 CACHE를 정의하자.

• CACHE[s][e] = s ... e 번째 수가 palindrome인가?

점화식은 아래와 같다.

• CACHE[s][e] = (CACHE[s+1][e-1] && N[s] == N[e]) ? 1 : 0

#include <iostream>

using namespace std;

int32_t N, M;
int32_t NUMBER[2000];
uint8_t CACHE[2000][2000];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N;
  for (int it = 0; it < N; ++it)
  {
    cin >> NUMBER[it];
  }

  // DP
  for (int s = 0; s < N; ++s)
  {
    CACHE[s][s] = 1;
  }

  for (int s = N - 2; s >= 0; --s)
  {
    for (int e = s + 1; e < N; ++e)
    {
      if (s + 1 <= e - 1)
      {
        CACHE[s][e] = (CACHE[s + 1][e - 1] && NUMBER[s] == NUMBER[e]) ? 1 : 0;
      }
      else
      {
        CACHE[s][e] = (NUMBER[s] == NUMBER[e]) ? 1 : 0;
      }
    }
  }

  // Solve
  cin >> M;
  for (int it = 0; it < M; ++it)
  {
    int s, e;
    cin >> s >> e;
    cout << (int)CACHE[s - 1][e - 1] << '\n';
  }

  return 0;
}