Boj 1695) 팰린드롬 만들기

문제

백준 1695

설명

문자열 \(S\) 의 \(j\) 번째 인덱스에서 시작하는 길이가 \(i\) 인 부분문자열이 팰린드롬이 되기위해 끼워넣어야 하는 수의 갯수를 \(D_{(i, j)}\) 라고 하자. 그러면 다음 점화식을 얻을 수 있다.

\[D_{(i, j)} = \begin{cases} D_{(i-2, j+1)},& \text{if } S[j] = S[j+i] \\ \\ \mathrm{min}(D_{(i-1, j)}, D_{(i-1, j+1)}) + 1 ,& \text{else } \end{cases}\]

위 점화식을 설명하자면 다음과 같다.

• 펠린드롬이 성립하려면 양쪽 끝이 같아야한다.
• 만약 양쪽 끝이 같으면 새로 수를 추가할 필요가 없다.
• 만약 다른경우 한쪽에 다른쪽의 숫자를 추가해야한다. 양쪽 중 어느쪽에 붙이는게 최적인지는 알 수 없으므로 하나하나 비교한다.

또한 점화식의 특징을 이용해 dp[] 를 3개 만들어서 돌려써서 메모리를 아낄 수 있다.

시간 복잡도

O(n^2)

코드

int arr[5001], dp1[5001], dp2[5001], dp3[5001];

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	for (int i = 0; i < n - 1; i++)
		dp1[i] = arr[i] != arr[i + 1];
	
	for (int i = 2; i < n; i++)
	{
		copy(dp2, dp2 + n, dp3);
		copy(dp1, dp1 + n, dp2);
		for (int j = 0; j + i < n; j++)
		{
			if (arr[j] == arr[j + i])
				dp1[j] = dp3[j+1];
			else
				dp1[j] = min(dp2[j], dp2[j + 1]) + 1;
		}
	}
	
	cout << dp1[0];

}