[백준] 10942번 팰린드롬? C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;

int n, a[2003],m,x,y,dp[2003][2003];

int go(int x, int y) {
  if(x >= y) return 1; // x가 y보다 커지면 true
  int &ret = dp[x][y];
  if(ret != -1) return ret;
  if(a[x] == a[y]) { 
    // 같으면 계속해서 확인
    ret = go(x + 1, y - 1);
  } else {
    // 다르면 0 반환
    ret = 0;
  }
  return ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  cin >> m;
  memset(dp, -1, sizeof(dp));
  for(int i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    y--;
    cout << go(x, y) << '\n';
  }
  return 0;
}

풀이

반복해서 같은 작업을 반복하기 때문에, 상태값을 저장하면 편리하다. 가장 앞과 맨 뒤의 값을 비교하면서 다른 값이 나오면 0을, 같은 값이 나오면 계속해서 확인하는 과정을 취한다. 만약 x값이 y보다 커지는 경우는 팰린드롬이다.