단어 게임
시간 제한2초메모리 제한128 MB
문자열과 단어 사전이 주어질 때, 남은 문자들이 순서를 유지하며 사전 단어들의 연결이 되도록 삭제해야 하는 최소 문자 수를 구합니다.
문제
w개의 단어가 들어 있는 사전이 주어진다. 사전의 모든 단어는 영어 소문자 a부터 z까지만으로 이루어져 있으며, 각 단어의 길이는 25 이하이다.
또한 길이가 l인 문자열 S가 주어진다. S에서 몇 개의 문자를 지우면, 남은 문자열을 사전에 있는 단어들을 이어 붙인 형태로 표현할 수 있다. 지우지 않은 문자들의 순서는 원래 S에서의 순서를 그대로 유지해야 한다.
S를 사전 단어들로 표현할 수 있게 만들기 위해 지워야 하는 문자의 최소 개수를 구하라.
입력
첫째 줄에 w와 l이 주어진다 (1 <= w <= 600, 2 <= l <= 300).
둘째 줄에는 문자열 S가 주어진다.
이어지는 w개의 줄에는 사전의 단어가 한 줄에 하나씩 주어진다.
출력
S에서 지워야 하는 문자의 최소 개수를 출력한다.
힌트
browndcodw에서 두 개의 d를 지우면 browncow가 남고, 이는 사전 단어 brown과 cow 두 개로 표현할 수 있다.