[백준/C,C++] 10942번: 팰린드롬?

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

10942번: 팰린드롬?

풀이

1, 2, 1, 3, 1, 2, 1로 예를 들어보겠습니다.

 

S = 1, E = 7일 경우 1과 1이 같고 그 중간 범위인 2, 1, 3, 1, 2가 팰린드롬이면 팰린드롬입니다.

 

S = 2, E = 6일 경우 2와 2가 같고 그 중간 범위인 1, 3, 1이 팰린드롬이면 팰린드롬입니다.

 

S = 3, E = 5일 경우 1과 1이 같고 그 중간 범위인 3이 팰린드롬이면 팰린드롬입니다.

 

수가 하나일 경우 무조건 팰린드롬이므로 S = 1, E = 7인 경우에는 팰린드롬이라고 볼 수 있습니다.

 

이를 재귀로 나타내면 해결할 수 있는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX = 2001;

int N, M, S, E;
int nums[MAX];
int cache[MAX][MAX];

int func(int a, int b)
{
    // 펠린드롬인지 아닌지 이미 판단 되었다면 그 값을 반환
    if (cache[a][b] != -1) {
        return cache[a][b];
    }

    // 같지 않다면 펠린드롬이 아님
    if (nums[a] != nums[b]) {
        return cache[a][b] = 0;
    }
    // 같다면 S, E의 범위를 줄여 재귀 호출
    else {
        return cache[a][b] = func(a + 1, b - 1);
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(cache, -1, sizeof(cache));

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> nums[i];
        // 자기 자신은 펠린드롬
        cache[i][i] = 1;
        // 인접한 수와 같다면 펠린드롬
        if (nums[i] == nums[i - 1]) {
            cache[i - 1][i] = 1;
        }
        // 아니라면 펠린드롬이 아님
        else {
            cache[i - 1][i] = 0;
        }
    }

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> S >> E;
        cout << func(S, E) << '\n';
    }

    return 0;
}

반례

Input

11
1 2 1 7 1 5 1 7 1 2 1
5
1 11
2 9
2 10
4 5
4 8

Output

1

0

1

0

1