Boj 1695) 팰린드롬 만들기
문제Permalink
설명Permalink
문자열
위 점화식을 설명하자면 다음과 같다.
- 펠린드롬이 성립하려면 양쪽 끝이 같아야한다.
- 만약 양쪽 끝이 같으면 새로 수를 추가할 필요가 없다.
- 만약 다른경우 한쪽에 다른쪽의 숫자를 추가해야한다. 양쪽 중 어느쪽에 붙이는게 최적인지는 알 수 없으므로 하나하나 비교한다.
또한 점화식의 특징을 이용해 dp[] 를 3개 만들어서 돌려써서 메모리를 아낄 수 있다.
시간 복잡도Permalink
O(n^2)
코드Permalink
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];
}
댓글남기기