1695번 - 팰린드롬 만들기
#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; }
웬만한 케이스에선 문제없이 돌아가는 듯 합니다.
근데 어디가 문제인지 계속 오류가 나는데 반례를 구상하지도 못하겠습니다.
반례만이라도 찾아주시면 너무나 감사하겠습니다ㅠㅠ
6
1 2 2 2 1 2
올바른 정답: 1
출력: 2
사랑해요
댓글을 작성하려면 로그인해야 합니다.
yoonjong1820 3년 전
웬만한 케이스에선 문제없이 돌아가는 듯 합니다.
근데 어디가 문제인지 계속 오류가 나는데 반례를 구상하지도 못하겠습니다.
반례만이라도 찾아주시면 너무나 감사하겠습니다ㅠㅠ