문제 링크
문제
티어: 골드 1
알고리즘: dp
단어가 w개 실린 사전이 하나 주어진다. 사전에 실린 단어들은 모두 a에서 z까지의 알파벳 소문자들로만 이루어져 있고, 길이는 각각 25자 이하이다.
길이가 l인 문자열 S도 하나 주어진다. 이 문자열에서 몇 개의 문자를 제거하면, 나머지를 사전에 실린 단어들로 표현해 낼 수 있다. 표현해 낼 수 있다는 것이 무슨 뜻인지는, 입출력 예시를 통해 이해하면 된다.
여러분이 할 일은 이렇게 사전에 실린 단어들로 이 문자열을 표현해 내기 위해, 문자열에서 제거해야 하는 문자의 최소 개수가 몇 개인지 계산하는 것이다.
입력
첫째 줄에 w와 l이 주어진다. (1 ≤ w ≤ 600, 2 ≤ l ≤ 300) 두 번째 줄에는 문자열 S가 주어진다. 이어지는 w개의 줄에는 사전 내의 각 단어가 한 줄에 한 개씩 주어진다.
출력
첫 줄에, S에서 제거해야만 하는 최소한의 문자 개수를 출력한다.
풀이
사전에 실린 단어들로 S 문자열을 표현해 내기 위해, 문자열에서 제거해야 하는 문자의 최소 개수 개수를 출력해야 한다.
결국 목표는 S 문자열을 사전 단어들의 연속으로 표현하는 것이다.
예를 들어 browncow처럼 말이다.
그러면 단어 하나 하나를 처음부터 매칭시키면 되지 않을까? 라는 생각이 든다.
단어 하나 하나를 매칭시킴으로써 S 문자열을 사전 단어들의 연속으로 표현해 보는 것이다.
예제 입력 1을 보면,
6 10
browndcodw
cow
milk
white
black
brown
farmer
사전 단어 6개를 매칭해 본다. 이러한 사전단어가 처음으로 매칭된다면, S 문자열의 맨 앞 단어가 될 것이다. 그렇기 때문에 매칭되는 지점은 최초의 지점이다.
예를 들어 cow를 처음으로 매칭한다면, (brownd)co(d)w ()가 제거되고 cow만 남게 될 것이다.
매칭이 된 이후에는 다음 매칭해야 될 S의 구간이 나오는데, 만약 이 구간이 같다면 최소 횟수를 가진 상태만 매칭을 확인하면 되지 않을까?
예를 들어 xxxxxx/cods -> /까지 3회와 5회가 있으면 3회만 경우를 따져보는 것이다. 그러면 불필요한 횟수는 줄여줄 수 있다.
이를 토대로 dp를 정의하면, dp[A] -> A는 어디까지 매칭되었는지를 의미하고, dp[5]의 의미는 1부터 5까지 매칭되었을 때 최소 횟수가 된다.
이러한 풀이 말고, 5까지 매칭을 구하고자 할 때 매칭 된 1 ~ 4의 경우로 구하는 풀이도 가능할 것이다. 하지만 이 풀이 또한 dp의 정의는 같다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static final int MAX = Integer.MAX_VALUE;
static int w, l;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
String S = " " + br.readLine(); // 1 ~ l까지`
int[][] dp = new int[l + 1][2]; // 1은 이미 진행했음을 의미
init(dp);
dp[0][0] = 0;
String[] dictionary = new String[w];
for(int i=0; i<w; i++) {
dictionary[i] = br.readLine();
}
boolean end = false;
while(!end){
if(!start(S, dictionary, dp)) {
end = true;
}
}
int answer = MAX;
for(int i=1; i<=l; i++) {
if(dp[i][0] != MAX) {
answer = Math.min(answer, dp[i][0] + (l - i));
}
}
System.out.println(answer);
}
static boolean start(String S, String[] dictionary, int[][] dp) {
boolean isNext = false;
for(int i=0; i<l; i++) {
if(dp[i][0] != MAX && dp[i][1] != 1) {
for(int j=0; j<w; j++) {
int cnt = 0;
//사전의 단어를 하나씩 매칭시켜 본다.
int stdCursor = 0;
String std = dictionary[j];
for(int k=i + 1; k<=l; k++) {
if(std.charAt(stdCursor) == S.charAt(k)) {
stdCursor += 1;
if(stdCursor == std.length()) {
//매칭 완료
if(dp[i][0] + cnt < dp[k][0]) {
dp[k][0] = dp[i][0] + cnt;
dp[k][1] = 0;
isNext = true;
}
break;
}
} else {
cnt += 1; //제거
}
}
}
dp[i][1] = 1;
}
}
return isNext;
}
static void init(int[][] dp) {
for(int i=0; i<dp.length; i++) {
dp[i][0] = MAX;
}
}
}