[BOJ-21925 ] 짝수 팰린드롬(C++)

 

백준 21925 짝수 팰린드롬

 

21925번: 짝수 팰린드롬

 

문제 설명

 

 - 길이가 N인 수열 A가 있다.

 

 - 이 수열을 여러 개의 짝수 팰린드롬으로 나누려 한다.

 

 - 짝수 팰린드롬이란 길이가 짝수이고, 뒤집기 전과 후가 같은 문자열을 말한다.

 

 - 짝수 팰린드롬을 최대한 많이 있도록 나누려고 할 때 짝수 팰린드롬은 최대 몇 개가 있는지 구하라

---

 

입력 값

 

 - 첫 번째 줄에 수열 A의 길이 N이 주어진다.

  ( 1 <= N <= 5,000 / N은 항상 짝수이다.)

 

 - 다음 줄에는 총 N개의 수열 A 원소, Ai가 주어진다. ( 1<= Ai <= 10,000 )

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 주어진 수열로 만들 수 있는 짝수 팰린드롬의 최대 개수를 구하는 문제이다.

 

 - 주어진 수열의 부분 수열로 만들기 때문에 앞에서부터 짝수 팰린드롬을 만들어야 한다.

 

 - 맨 앞에서 짝수 팰린드롬을 만들 수 없다고 하면, 나눌 수 없게 된다.

 

 - 즉, 이 문제는 앞에서부터 짝수 팰린드롬을 만들어고, 그것의 최대 개수를 리턴하면 된다.

 

 - 다만, 이 문제를 잘 살펴보면 짝수 팰린드롬을 만들 수 있는 제일 처음 위치가 같은 경우

   해당 위치에서 시작하는 짝수 팰린드롬의 최대 개수는 항상 같다는 것이다.

 

 - 위 그림에서 표시된 시작 위치부터 짝수 팰린드롬의 최대 개수를 구한다고 해보자.

 

 - 앞에 만든 짝수 팰린드롬이 위 그림처럼 만들어져도, 

 

 - 위 그림처럼 만들어져도, 시작 위치는 같기 때문에 뒤에 나오는 개수는 같게 된다.

 

 - 즉, 이 문제는 시작 위치에 따라 항상 같은 값을 계산하기 때문에 반복 작업이 수행된다.

 

 - 그래서 이 문제는 DP 문제라고 볼 수 있다.

 

 - 수식으로 표현해보면,

   D[i] = i번째를 시작으로 하는 짝수 팰린드롬의 최대 개수.

   D[i] = max ( 1, 1 + D[i+2] , 1 + D[i+4], ... , 1 + D[i+k] ) 이다.

   1은 i번쨰를 시작해서 끝까지 선택하여 팰린드롬을 만드는 경우

   1+D[i+2]는 i~i+1을 팰린드롬으로 만들고, i+2부터 최대 팰린드롬을 만드는 경우

   1+D[i+k]는 i~i+k-1을 팰린드롬으로 만들고, i+k부터 최대 팰린드롬을 만드는 경우이다.

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int N;
int boards[5001];

int dp[5001];

int evenPalindrome(int start) {

	if (start >= N) {
		return 0;
	}
	if (dp[start] != 0) {
		return dp[start];
	}

	int result = -1;

	for (int i = start + 1; i < N; i += 2) {

		bool isPalindrome = true;

		for (int j = 0; j <= (i - start) / 2; j++) {

			if (boards[start + j] != boards[i - j]) {
				isPalindrome = false;
				break;
			}

		}
		if (isPalindrome) {

			int value = evenPalindrome(i + 1);
			if (value == -1) {
				continue;
			}
			result = max(result, value+1);

		}

	}

	return dp[start]=result;

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		boards[i] = a;
	}

	cout << evenPalindrome(0) << endl;

	return 0;
}