백준 1053(팰린드롬 공장)

www.acmicpc.net/problem/1053

1053번: 팰린드롬 공장

진짜 대단하다 컴퓨터는 

이 문제를 풀면서 컴퓨터는 진짜로 대단하다는 걸 느낀다. 사람이라면 조건을 다 따져서 하드코딩해야 하는 것을 컴퓨터는 그냥 다 해보면 된다. 

 

그리고 dp는 더 아름답다.

 

이 문제는 dp이다. 태그에서 찾았기 때문에 dp인걸 알았지만 어떻게 풀어야 할지 감이 안 왔었다. 

 

그러다가 그냥 하면 되지 않나 생각이 드는 순간 감이 왔다. 

 

일단 우리는 팰린드롬인지 아닌지를 생각할 필요가 별로 없다. 

이게 제일 중요한 핵심인듯하다. 

할 수 있는 모든 것을 하면 된다. 

 

처음에 제일 중요한 생각은 4.의 과정인 단 한 번밖에 못 쓰는 특수케이스를 먼저 모든 경우에 대해서 처리해주겠다는 생각이 들어야 한다. 

 

50개의 문자열에서 서로다른 두개를 뽑아 봤자 n^2을 넘지 않는다. 

근데 이제 의문이 생길 수 있다. 

 

이걸 먼저하면 안되지 않을까 

 

하지만 이것은 좀 자명하다 교환을 한다는 것은 예시처럼 babacvabba 아다리가 맞아야 다른 연산을 하는 것보다 연산이 한 번 줄게 된다. 이거에 대해선 더 얘기하지 말자. 

 

가장 중요한 dp[][]는 이중배열이다. dp[i][j]에는 i,j까지 팰린드롬으로 만드는데 드는 최소비용을 저장한다.

 

그러고 이제 할 수 있는 연산

삽입, 삭제, 교환을 생각해보자

 

이것을 먼저 생각하자는 이유는 우리는 삽입,삭제,교환을 연산을 하고나서 다음 index로 진행을 할 것인데 이 연산이 어떤 연산인가에 따라서 index조정해야하기 때문이다. 

 

삽입을 하는 것을 잘 생각해보자 abaa에서 왼쪽에 a를 삽입하나 오른쪽 a를 삭제하나 똑같은 결과를 가져온다. 

 

따라서 삽입과 삭제는 같은 연산으로 봐도 좋다.

교환은 bcaqec

에서 b,c 중 하나를 교환하고 나면 당연히 c와 e로 이동한다. 

 

 

dp[l][r]에서 

왼쪽 삽입 오른쪽 삭제는 dp[l][r-1] 로 이동하고, 오른쪽 삽입 왼쪽 삭제는 dp[l+1][r]로 이동, 

교환은 dp[l+1][r-1]로 이동한다. 

 

따라서 dp[l][r] = min(dp[l][r-1], dp[l+1][r], dp[l+1][r-1])+1 이라고 할 수 있는데

 

교환할 때를 생각해보면 만약 두 수가 같으면 비용이 발생하지 않는다. 

 

따라서 

 

dp[l][r] = min(dp[l][r-1]+1, dp[l+1][r]+1, dp[l+1][r-1])+(s[l]!=s[r]))

이 된다. 

 

다시한번 얘기하지만 우리는 가능성만 생각하면 된다. 굳이 그리디적인 사고과정을 복잡하게 할 필요가 없는 것 같다. 

 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 55
#define INF 987654321

int dp[MAX][MAX];
string s;

int solve(int l, int r, string a) {
	if (dp[l][r] != -1)return dp[l][r];
	if (l >= r) return 0;
	int &ret = dp[l][r];
	ret = min({ solve(l + 1, r, a) + 1, solve(l, r - 1, a) + 1, solve(l + 1, r - 1, a) + (a[l] != a[r]) });
	
	return ret;
}

int main() {
	cin >> s;
	memset(dp, -1, sizeof(dp));
	int ans = solve(0, s.size() - 1, s);
	for (int i = 0; i < s.size(); i++) {
		for (int j = i+1; j < s.size(); j++) {
			memset(dp, -1, sizeof(dp));
			string tmp = s;
			swap(tmp[i], tmp[j]);
			ans = min(ans, solve(0, s.size() - 1, tmp) + 1);
		}
	}
	cout << ans;

}