[ BOJ ][JAVA][1053] 팰린드롬 공장

https://www.acmicpc.net/problem/1053

1053번: 팰린드롬 공장

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	848	259	215	32.526%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

babacvabba

예제 출력 1

2

예제 입력 2

abba

예제 출력 2

0

예제 입력 3

dabba

예제 출력 3

1

접근

dp문제는 dp배열의 요소에 원하는 결과값을 저장해야 한다는 사실을 정확히 짚고 구성해야함을 다시 한번 잊지말자.

이 문제는 도저히 어떻게 풀지 감을 잡지 못했다..

 

여러 블로그를 참조하면서 알아낸 충격적인 사실은 디피를 구성할 때 팰린드롬인지 아닌지를 생각할 필요가 없는 것이다. 

단지, 연산이 가능한 가능성을 저장해두는 것이다.

 

왼쪽 삽입 오른쪽 삭제는 dp[l][r-1], 오른쪽 삽입 왼쪽 삭제는 dp[l+1][r], 교환은 dp[l+1][r-1]이 된다.

따라서 이 중의 최솟값을 찾으면 된다.

 

그리고 4번 연산은 한번만 사용할 수 있는데 생각해보면 다른 연산보다 가장 먼저 하면 된다. 그렇지 않으면 이미 다른 연산이 일어날때 4번연산이 소용없어지므로.

 

참고 : https://bongssi.tistory.com/entry/%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EA%B3%B5%EC%9E%A5

코드

/**
 * BOJ 1053 팰린드롬 공장
 * DP
 */
import java.io.*;
import java.util.*;

/**
 * dp[l][r] : l에서 r까지 팰린드롬으로 만드는데 드는 최소비용
 */
public class p1053 {
    static String input;
    public static void main(String[] args) throws IOException {
        init();
        pro();
    }
    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
    }
    static void pro() {
        char[] pelindrome = input.toCharArray();
        int ans = solution(pelindrome); // 원래 문자열에서 팰린드롬을 만드는 법

        char[] tmp = new char[pelindrome.length];
        for (int i = 0; i < pelindrome.length - 1; i++) {
            for (int j = i + 1; j < pelindrome.length; j++) {
                if (pelindrome[i] == pelindrome[j]) continue;

                tmp = pelindrome;
                swap(i, j, tmp);
                ans = Math.min(ans, solution(tmp) + 1);
                swap(i, j, tmp);
            }
        }
        System.out.println(ans);
    }

    static int solution(char[] line) {
        int size = line.length;
        int[][] dp = new int[size][size];
        for (int i = 0; i < size; i++) {
            dp[i][i] = 0;
            if (i != size - 1) {
                dp[i][i + 1] = line[i] == line[i + 1] ? 0 : 1;
            }
        }

        for (int i = 2; i < size; i++) {
            for (int j = 0; j < size - i; j++) {
                dp[j][j + i] = Math.min(dp[j + 1][j + i] + 1, dp[j][j + i - 1] + 1);
                if (line[j + i] == line[j]) {
                    dp[j][j + i] = Math.min(dp[j + 1][j + i - 1], dp[j][j + i]);
                } else {
                    dp[j][j + i] = Math.min(dp[j + 1][j + i - 1] + 1, dp[j][j + i]);
                }
            }
        }
        return dp[0][size - 1];
    }

    static void swap(int a, int b, char[] line) {
        char temp = line[a];
        line[a] = line[b];
        line[b] = temp;
    }
}