팰린드롬?

백준 10942번: 팰린드롬?

아이디어

cache[start][end]에 메모이제이션 ㄱㄱ
start와 end에 위치한 문자가 같고, 그 두개를 뺀 문자열이 팰린드롬이면 start ~ end도 팰린드롬이다.
Base case는 문자가 하나이거나 두개인 경우.

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int arr[2000];
int cache[2000][2000];

int solve(int start, int end) {
    if (start == end) return 1;
    if (end - start == 1 && arr[start] == arr[end]) return 1;

    int& ret = cache[start][end];
    if (ret != -1) return ret;

    ret = (arr[start] == arr[end]) && solve(start+1, end-1);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    memset(cache, -1, sizeof(cache));
    int s, e;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        cout << solve(s-1, e-1) << '\n';
    }
    return 0;
}

여담

집컴에 올려놓은 code-server로 푸니까 기분이 좋다. 불쌍하게 구름이나 onlinegdb로 풀었는데 이제 안그래도 된다. 이균서 병장님 감사합니다~~