[C++] 10942번 팰린드롬? - DP

#include <iostream>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 2001

using namespace std;

int N, M;  //수열의 크기 N, 질문의 개수 M
int num[MAX_N];  //수열
int memo[MAX_N][MAX_N];  //메모
int S, E;  //질문

void input()
{
    cin >> N;
    LOOP(i, N) cin >> num[i];
    cin >> M;
}

int f(int l, int r)
{
    if(memo[l][r]) return memo[l][r];  //이미 탐색함
    //탐색하지 않음
    
    if(!(r-l)) return memo[l][r]= 2;
    if(r-l<=1) return memo[l][r]= (num[r]==num[l] ? 2:1);
    return memo[l][r] = ((f(l+1, r-1)==2) && num[r]==num[l]) ? 2:1;  //DP
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    while(M--) {
        cin >> S >> E;
        cout << f(S, E)-1 << '\n';
    }
    
    return 0;
}

 

<알고리즘>

1. {S, E}를 보기 위해 {S+1, E-1}을 본다. {S+1, E-1}이 false라면 {S, E}도 false고, {S+1, E-1} && (S, E)가 true라면 {S, E}도 true이다.

재귀함수를 하는 것보다 배열로 해서 제일 작은 크기인 1, 2개부터 시작하면 재귀함수를 사용할 필요가 없어서 시간이 절약된다. 이렇게 푼 다른 사람의 코드가 있어서 가져왔다.

 

 

<참고 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/35669807

로그인

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.