문제 링크
문제
티어: 골드 3
알고리즘: dp
형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다.
이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 바꿀 수 있다.
따라서, 한 문장을 여러 가지 방법으로 해석할 수 있다. 이때 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다. 문장과 단어는 알파벳 소문자로만 이루어져 있다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 문장을 해석할 수 없다면 -1을 출력한다.
풀이
문장을 해석하는 여러 가지 비용 중 최솟값을 출력해야 한다.
그러니까 단어를 어떻게 바꿔서 어떤 부분에 포함하는 지에 따라서 다양한 경우가 나오는데 당연히 완탐은 불가능하다.
선택이 다음 선택에 영향을 주기 때문에 그리디도 아니다.
그래서 이런 경우 dp로 풀 수 있다.
예제 입력 1을 보면
neotowheret를 해석하는 최소 비용을 구해야 한다.
순차 탐색을 하는 과정에서 2번 째 인덱스를 탐색하는 상황을 보면,
새로 탐색하는 문자가 o이며, 이 때 새로운 경우의 수는
1. o
2. eo
3. neo
가 된다.
1번 o일 때는 ne까지의 최소 비용을 더해주면 된다. dp[2]
2번 eo일 때는 n까지의 최소 비용을 더해주면 된다. dp[1]
3번 neo일 때는 neo의 최소 비용을 구해주면 된다.
순차 탐색을 하면서 ne, n의 최소 비용은 한 번 구하기 때문에 또 구할 필요가 없다. 그래서 이 부분을 메모제이션해야 한다.
그래서 dp[A]는 맨 앞에서부터 A까지 최소 비용이라고 정의할 수 있다.
그리고 구현해야 될 함수는 크게 두 가지다.
-
최소 비용을 구하는 문자열(neo)의 문자들을 포함하고 길이가 같은 단어를 찾는 함수.
-
찾은 단어에서 문자열(neo)로 변환하는데 드는 비용 (비용은 간단하다. 두 문자열의 같은 위치를 비교하면서 다르다면 비용이 1씩 올라간다.)
이 함수들과 dp를 정의했다면 구현은 간단하다. 자세한 구현 방법은 코드를 참고하길 바란다.
이 풀이의 시간 복잡도는 약 O(50^3) 정도다.
소스 코드
import java.io.*;
import java.util.*;
class Word {
String s;
int[] wc; //word count;
Word(String s) {
this.s = s;
wc = new int[26];
fillWc(this.s, this.wc);
}
static void fillWc(String str, int[] wordCount) {
for(int i=0; i<str.length(); i++) {
wordCount[transCharToInt(str.charAt(i))] += 1;
}
}
static int transCharToInt(char c) {
return (int) c - 97;
}
}
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int N = Integer.parseInt(br.readLine());
ArrayList<Word> wList = new ArrayList<>();
for(int i=0; i<N; i++) {
wList.add(new Word(br.readLine()));
}
int[] dp = new int[str.length() + 1];
for(int i=1; i<=str.length(); i++) {
int cost = Integer.MAX_VALUE;
for(int j=i - 1; j>=0; j--) {
if(dp[j] != -1) {
//앞에 분할된 부분이 단어로 만들어질 수 있다면
String leftStr = str.substring(j, i);
ArrayList<Word> list = new ArrayList<>();
for(int k=0; k<N; k++) {
//가능한 단어를 일단 넣어준다.
if(isInclude(leftStr, wList.get(k))) {
list.add(wList.get(k));
}
}
if(list.size() != 0) {
//가능한 단어가 있다면 그 중 가장 작은 비용을 구한다.
int min = Integer.MAX_VALUE;
for(int k=0; k<list.size(); k++) {
min = Math.min(min, findCost(leftStr, list.get(k).s));
}
cost = Math.min(cost, dp[j] + min);
}
}
}
dp[i] = cost;
if(cost == Integer.MAX_VALUE) {
dp[i] = -1;
}
}
System.out.println(dp[str.length()]);
}
static boolean isInclude(String stdStr, Word w) {
//포함되었는지 체크하는 함수.
int[] copyWc = new int[26];
for(int i=0; i<26; i++) {
copyWc[i] = w.wc[i];
}
for(int i=0; i<stdStr.length(); i++) {
int ind = Word.transCharToInt(stdStr.charAt(i));
copyWc[ind] -= 1;
}
for(int i=0; i<26; i++) {
if(copyWc[i] != 0) {
return false;
}
}
return true;
}
static int findCost(String stdStr, String word) {
//이 함수에 들어오는 두 단어는 길이도 같으며 요소도 같음 (isInclude를 통과함)
int result = 0;
for(int i=0; i<stdStr.length(); i++) {
if(stdStr.charAt(i) != word.charAt(i)) {
result += 1;
}
}
return result;
}
}