10-12: 최소비용 팰린드롬

최소비용 팰린드롬

 

문제

---

팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 우리는 두 가지 연산을 할 수 있다. 첫 째로는, 하나의 문자를 삽입하는 것이며, 둘 째로는 기존에 문자열 내에 존재하는 하나의 문자를 삭제하는 것이다. 이 두가지 연산을 통하여 주어진 문자열을 팰린드롬으로 만들 수 있다. 하나의 문자를 삽입 또는 삭제하기 위해서는 비용이 들어가며, 이는 각 알파벳마다 다르다. 문자열이 주어지고, 각 알파벳을 삽입할 때의 비용, 삭제할 때의 비용이 주어질 때, 주어진 문자열을 팰린드롬으로 만들기 위한 최소 비용을 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 문자열의 길이 N, 문자열 내에 존재하는 문자의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 두 번째 줄에는 문자열이 주어진다. 세 번째 줄부터 각 문자를 삽입, 삭제하는데 드는 비용이 주어진다. 이는 “a b c” 형식으로 주어지며, 그 뜻은 알파벳 a를 삽입하는데는 b, 삭제하는데는 c 만큼의 비용이 든다는 것을 의미한다. (문자열은 알파벳 소문자로만 구성되어있다.)  

출력

---

주어진 문자열을 팰린드롬으로 만들기 위한 최소 비용을 출력한다.

 

예제 입력

4 3
abcb
a 1000 1100
b 350 700
c 200 800

예제 출력

900

 

설명

bcbabcb 로 팰린드롬을 만드는 것이 900 만큼의 비용이 들며, 이것이 최소 비용이다.

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

public class dp_palindrome_lc {

    /**
     * 팰린드롬 만들기
     * 문제:
     * 팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다.
     * 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 우리는 두 가지 연산을 할 수 있다.
     * 첫 째로는, 하나의 문자를 삽입하는 것이며, 둘 째로는 기존에 문자열 내에 존재하는 하나의 문자를 삭제하는 것이다. 이 두가지 연산을 통하여 주어진 문자열을 팰린드롬으로 만들 수 있다.
     * 하나의 문자를 삽입 또는 삭제하기 위해서는 비용이 들어가며, 이는 각 알파벳마다 다르다. 문자열이 주어지고, 각 알파벳을 삽입할 때의 비용, 삭제할 때의 비용이 주어질 때, 주어진 문자열을 팰린드롬으로 만들기 위한 최소 비용을 출력하는 프로그램을 작성하시오.
     *
     * 입력: 첫 번째 줄에 문자열의 길이 N, 문자열 내에 존재하는 문자의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 두 번째 줄에는 문자열이 주어진다.
     * 세 번째 줄부터 각 문자를 삽입, 삭제하는데 드는 비용이 주어진다. 이는 “a b c” 형식으로 주어지며, 그 뜻은 알파벳 a를 삽입하는데는 b, 삭제하는데는 c 만큼의 비용이 든다는 것을 의미한다. (문자열은 알파벳 소문자로만 구성되어있다.)
     *
     *
     * 출력: 주어진 문자열을 팰린드롬으로 만들기 위한 최소 비용을 출력한다.
     *
     *
     * 예제 입력:
     * 4 3
     * abcb
     * a 1000 1100
     * b 350 700
     * c 200 800
     *
     *
     * 예제 출력: 900
     *
     *
     * @param args
     */

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String s1 = br.readLine();

        int[][] cost = new int[26][2];
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            char base = 'a';
            for (int j=0; j<2; j++){
                cost[c-base][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][]dp = new int[s1.length()][s1.length()];
        //let dp[i][j] be min cost 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 {
                  
                    int frontInsertCost = dp[j+1][i+j] + computeCost(cost, s1.charAt(j), true);
                    int endInsertCost = dp[j][i+j-1] + computeCost(cost, s1.charAt(i+j), true);
                    int frontDeleteCost = dp[j+1][i+j]+ computeCost(cost, s1.charAt(j), false);
                    int endDeleteCost =  dp[j][i+j-1] + computeCost(cost, s1.charAt(i+j), false);

                    dp[j][i+j] = Math.min(Math.min(frontInsertCost, endInsertCost), Math.min(frontDeleteCost, endDeleteCost));

                }
            }
        }


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



    }

    private static int computeCost(int[][] cost, char c, boolean isInsert) {
        char base = 'a';

        int index = c - base;
        int y = isInsert? 0:1;
        return cost[index][y];
    }
}