[C++] 백준 10942 - 팰린드롬? (동적계획법, 메모이제이션)

0. [c++] 백준

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

1. 풀이

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include<iostream> #include<cstring>    //memset을 활용하기 위해 선언   using namespace std;   int arr[2000];   //cache[i][j] = i에서 j까지 팰린드롬인가? int cache[2000][2000];   int dp(const int& front, const int& end) {     int& ret = cache[front][end];          //기저 사례 : 이미 탐색을 한 구간인 경우     if (ret != -1)         return ret;       int size = front - end;       //기저 사례 : 구간의 길이가 0인 경우     if (size == 0)         return ret = 1;     //기저 사례 : 구간의 길이가 1인 경우     else if (size == 1) {         if (arr[front] == arr[end])             return ret = 1;     }     //구간의 길이가 1보다 큰 경우     else {         int before_step = dp(front + 1, end - 1);         if (before_step == 1 && arr[front] == arr[end]) {             return ret = 1;         }     }       return ret = 0; }   int main() {     ios::sync_with_stdio(0);     cin.tie(0);       int N, M, a, b;       cin >> N;       for (int i = 0; i < N; i++) {         cin >> arr[i];     }       memset(cache, -1, sizeof(cache));         cin >> M;     for (int i = 0; i < M; i++) {         cin >> a >> b;         cout << dp(a - 1,b - 1) << "\n";     }   } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!