yoonjong1820   3년 전

#include <iostream>
#include <cstring>
using namespace std;
int memo[5001][5001];
int palindrome(int from, int to, int arr[]){
    if (from+1==to && arr[from]!=arr[to]) return 1;
    else if (from+1==to && arr[from]==arr[to]) return 0;
    
    if (from > to || from == to) return 0;
    else{
        if (memo[from][to]!=-1){
            return memo[from][to];
        }
        
        if (arr[from]==arr[to]){ // 양쪽 끝 같을 때
            memo[from][to] = 0+palindrome(from+1, to-1, arr);
            return memo[from][to];
        }
        else{// 양 쪽 끝 다를 때
            int tmp1, tmp2;
            if (arr[from+1] == arr[to]){ //
                tmp1 = 1 + palindrome(from+2, to-1, arr);///
                memo[from][to] = tmp1;
                return memo[from][to];
            }
            else if (arr[from] == arr[to-1]){
                tmp2 = 1 + palindrome(from+1, to-2, arr);///
                memo[from][to] = tmp2;
                return memo[from][to];
            }
            else{
                tmp1 = 1+palindrome(from, to-1, arr);
                tmp2 = 1+palindrome(from+1, to, arr);
                if (tmp1<tmp2) memo[from][to] = tmp1;
                else memo[from][to] = tmp2;
                return memo[from][to];
            }
        }
    }
    
}
int main(){
    int n;
    cin>>n;
    int *arr;
    arr = new int[n];
    for (int i=0; i<n; i++){
        cin>>arr[i];
    }
    memset(memo, -1, sizeof(memo));

    cout<<palindrome(0, n-1, arr);
    
    
    return 0;
}

웬만한 케이스에선 문제없이 돌아가는 듯 합니다.

근데 어디가 문제인지 계속 오류가 나는데 반례를 구상하지도 못하겠습니다.

반례만이라도 찾아주시면 너무나 감사하겠습니다ㅠㅠ

devbelly   3년 전

6

1 2 2 2 1 2

올바른 정답: 1

출력: 2

yoonjong1820   3년 전

사랑해요

댓글을 작성하려면 로그인해야 합니다.