시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 200 | 82 | 73 | 50.000% |
단어가 w개 실린 사전이 하나 주어진다. 사전에 실린 단어들은 모두 a에서 z까지의 알파벳 소문자들로만 이루어져 있고, 길이는 각각 25자 이하이다.
길이가 l인 문자열 S도 하나 주어진다. 이 문자열에서 몇 개의 문자를 제거하면, 나머지를 사전에 실린 단어들로 표현해 낼 수 있다. 표현해 낼 수 있다는 것이 무슨 뜻인지는, 입출력 예시를 통해 이해하면 된다.
여러분이 할 일은 이렇게 사전에 실린 단어들로 이 문자열을 표현해 내기 위해, 문자열에서 제거해야 하는 문자의 최소 개수가 몇 개인지 계산하는 것이다.
첫째 줄에 w와 l이 주어진다. (1 ≤ w ≤ 600, 2 ≤ l ≤ 300) 두 번째 줄에는 문자열 S가 주어진다. 이어지는 w개의 줄에는 사전 내의 각 단어가 한 줄에 한 개씩 주어진다.
첫 줄에, S에서 제거해야만 하는 최소한의 문자 개수를 출력한다.
6 10 browndcodw cow milk white black brown farmer
2
browndcodw에서 두 개의 d를 제거하면, brown과 cow 두 개의 단어로 표현할 수 있다.
Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO February 2007 Contest > Silver 1번