[백준/Baekjoon] 10942 팰린드롬? C++ :: Dynamic programming

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

10942번: 팰린드롬?

---

1. Logic

펠린드롬을 확인 할 때 문자를 뒤집어서 봤을 때 똑같으면 펠린드롬인데 이렇게 구현해버리면 시간복잡도가 2000 * 1000000 == 약 20억 정도 나오기 때문에 제한 시간 안에 풀지 못한다. 그래서 나는 재귀를 통해서 인덱스를 +1 -1씩 해주었고 펠린드롬이면 dp[start][end]에 1을 아니면 0을 넣어서 메모이제이션 해줬다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int dp[2001][2001];
vector<int> input;
int n;

int solve(int start, int end) {
    if(start >= end) return 1;

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

    if(input[start] != input[end]) return 0;

    ret = solve(start + 1, end - 1);

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset(dp, -1, sizeof(dp));
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

    //solve(0, n - 1);

    int num;
    cin >> num;

    for(int i = 0; i < num; i++) {
        int a, b;
        cin >> a >> b;

        cout << solve(a-1, b-1) << "\n";
    }
}

---

3. Feedback

DP는 언제 풀어도 구현 생각하기가 어려운 것 같다. 그냥 꾸준히 푸는 수 밖에 없어보인다ㅜ

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90