백준 10942번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
0.5초	256MB	골드 4

사진을 클릭하면 문제로 이동합니다.

---

풀이

 문제를 보고 고민하다가 dp임을 깨달은 문제였다. 어떤 문자열이 회문이라면, 양 옆의 문자를 하나씩 떼어내도 회문이다. 예를 들어 12321라는 회문의 양 끝을 떼어보면 232로 회문임을 알 수 있다. 이를 통해 dp점화식을 세울 수 있다. 이 문제에서는 수열이기 때문에, 수열로 바꿔보면, 수열 seq에 대해

dp[s][e] = seq[s] == seq[e] && dp[s+1][e-1]

 

이다. dp[s+1][e-1]은 재귀적으로 구할 수 있다. 또한, 길이 1의 부분수열은 항상 회문이기 때문에, dp[i][i]는 무조건 true이다. 이를 적용하여, [s, e] 구간을 좁혀가며 찾으면 된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
#define MAX 2001
using namespace std;

int n, m;
int seq[MAX], dp[MAX][MAX];
vector<pair<int,int>> query;

void input() {
    cin >> n;
    memset(dp, 0xff, sizeof(int)*MAX*MAX);
    for(int i = 1; i <= n; i++) {
        cin >> seq[i];
        dp[i][i] = true;
    }
    cin >> m; query.resize(m);
    for(auto& [s, e] : query) cin >> s >> e;
}

int sol(int s, int e) {
    if (dp[s][e] != -1) {
        return dp[s][e];
    }
    if (s >= e) {
        return 1;
    }

    return dp[s][e] = (seq[s] == seq[e] && sol(s + 1, e - 1));
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    input();
    for(auto& [s, e] : query) {
        cout << sol(s, e) << endl;
    }
}