백준 1053 팰린드롬 공장 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/1053

1053번: 팰린드롬 공장

문제

팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다.

모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다.

1. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능)
2. 어떤 위치에 있는 문자를 삭제
3. 어떤 위치에 있는 문자를 교환
4. 서로 다른 문자를 교환

1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 연산은 많아야 한 번 사용할 수 있다.

문자열이 주어졌을 때, 팰린드롬으로 만들기 위해 필요한 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 영어 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 문제의 정답을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이다.

문제를 읽어 보면 4번 연산에 대해 고민하게 될 텐데,

4번 연산은 한 번만 가능하고, 문자열의 최대 길이는 50이기 때문에,

입력받은 문자열에 대해 2중 for문으로 한 번씩 모두 바꿔보면 된다.

[과정1]. 이렇게 4번 연산을 사용하지 않은 문자열 + 4번 연산을 사용한 모든 경우의 문자열에 대해 탐색하면 된다.

이제 1,2,3 번 각각의 연산을 살펴보자.

dabba의 문자열에서,

1번 연산(삽입)을 하면

dabbad로 한 번 만에 팰린드롬을 만들 수 있다.

2번 연산(삭제)을 하면

d     abba로 한 번 만에 팰린드롬을 만들 수 있다.

3번 연산(교환)을 하면 한 번 만에 팰린드롬을 만들 수 없으니 3번 연산을 검사할 필요가 없을까?

우리는 3번 연산이 필요 없단 걸 알지만 컴퓨터는 모른다.

고로 일단 검사는 필요할 것이다.

 

즉, 과정1에서 구한 문자열에 대해 모두 1,2,3번 연산을 최소로 하여 팰린드롬을 만드는 경우를 찾아내면 된다.

string input = 입력받은 문자열,

dp[left][right] = 문자열의 left 인덱스에서 right 인덱스까지의 부분 문자열을 팰린드롬으로 만드는 데에 드는 최소 연산 횟수라 하자.

팰린드롬을 만들기 위해선 left, right의 두 문자를 비교해가며 문자열의 가운데까지 검사해야 한다.

left의 시작은 0일 거고, right의 시작은 문자열의 길이-1일 것이다.

input[left] == input[right]라면 이 두 문자는 건들 필요가 없으니 다음 순서인 left+1, right-1을 검사한다.

input[left] != input[right]라면 1,2,3번 연산을 검사해 볼 필요가 있다.

만약 left를 삭제한다면 left+1, right가 다음 순서이고,

right를 삭제한다면 left, right-1이 다음 순서이다.

만약 left에 right와 같은 문자를 추가한다면 left, right-1이 다음 순서이고,

right에 left와 같은 문자를 추가한다면 left+1,right이 다음 순서이다.

즉 left, right-1 와 left+1, right 두 가지의 다음 경우를 탐색하면 삭제 연산, 삽입 연산은 확인 가능하다는 것이다.

만약 left나 right를 어떠한 문자로 교환하게 된다면, left와 right의 문자가 같아지므로, left+1, right-1가 다음 순서가 될 것이다.

[과정2]. 이렇게 3가지 연산에 대해 검사하고, left와 right 문자가 같은 경우까지 검사하는 식은 다음과 같다.

dp[left][right] = min({  solve(left + 1, right) + 1, solve(left, right - 1) + 1 , solve(left+1, right-1)+(input[left]!=input[right])});

 

left와 right는 0과 문자열 길이-1에서 시작하여 문자열의 가운데를 향해 재귀적으로  left와 right의 문자가 같은지 검사하며 나아가면 된다.

left와 right가 같지 않다면 +1로 연산 횟수를 더해주고, 같다면 그냥 다음 탐색 순서로 넘어간다.

 

 

 

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

int answer;
string input;
int dp[50][50];
int solve(int left, int right) {
	if (dp[left][right] != -1) return dp[left][right];
	if (left >= right) return 0;
	dp[left][right] = min({  solve(left + 1, right) + 1, solve(left, right - 1) + 1 , solve(left+1, right-1)+(input[left]!=input[right])});
	return dp[left][right];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> input;
	
	memset(dp, -1, sizeof(dp));
	answer = solve(0, input.length() - 1);

	for (int i = 0; i < input.length() - 1; i++) {
		for (int j = i + 1; j < input.length(); j++) {
			memset(dp, -1, sizeof(dp));
			swap(input[i], input[j]);
			answer = min(answer, solve(0, input.length() - 1)+1);
			swap(input[i], input[j]);
		}
	}

	cout << answer;

	return 0;
}