10-11: 팰린드롬 만들기

팰린드롬 만들기

 

문제

---

팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 추가해야 하는 최소의 문자 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 문자열이 “abca” 로 주어질 경우, ‘b’만 추가하면 “abcba” 를 만들 수 있으므로, 이 때는 1개의 문자만 추가하면 된다. 또 다른 예로써, 문자열이 “adcba” 로 주어질 경우에는, 문자 2개를 추가해야 한다.

 

입력

---

첫 번째 줄에 문자열이 주어진다. 이 문자열의 길이는 1,000 을 넘지 않는다.  

출력

---

주어진 문자열을 팰린드롬으로 만들기 위해서 추가해야 하는 문자 개수의 최솟값을 출력한다.

 

예제 입력

adcba

예제 출력

2

 

예제 입력

abccbdbac

예제 출력

3

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class dp_palindrome {

    /**
     * 팰린드롬 만들기
     * 문제:
     * 팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다.
     * 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 추가해야 하는 최소의 문자 개수를 출력하는 프로그램을 작성하시오.
     * 예를 들어, 문자열이 “abca” 로 주어질 경우, ‘b’만 추가하면 “abcba” 를 만들 수 있으므로, 이 때는 1개의 문자만 추가하면 된다. 또 다른 예로써, 문자열이 “adcba” 로 주어질 경우에는, 문자 2개를 추가해야 한다.
     *
     * 입력: 첫 번째 줄에 문자열이 주어진다. 이 문자열의 길이는 1,000 을 넘지 않는다.
     *
     *
     * 출력: 주어진 문자열을 팰린드롬으로 만들기 위해서 추가해야 하는 문자 개수의 최솟값을 출력한다.
     *
     *
     * 예제 입력: adcba
     *
     *
     * 예제 출력: 2
     *
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();

        int[][]dp = new int[s1.length()][s1.length()];
        //let dp[i][j] be min num of chars needed for s1.substring(i~j+1) to be a palidrome

        //Initial condition:
        dp[0][0] = 0;

        //populate single chars: already palindromes.

        for (int i = 1; i<s1.length(); i++){

            for (int j=0; j<s1.length()-i; j++){
                if (s1.charAt(j) == s1.charAt(i+j)){
                    dp[j][i+j] = dp[j+1][i+j-1];
                } else {
                    dp[j][i+j] = 1 + Math.min(dp[j][i+j-1], dp[j+1][i+j]);
                }
            }
        }

        System.out.println(dp[0][s1.length()-1]);



    }
}