시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 269 | 83 | 58 | 26.606% |
2K개의 글자로 이루어진 단어 N개가 주어진다.
코코스는 글자 하나를 포함하고 있는 정점으로 이루어진 유향 그래프(Directed graph)를 말한다. 이때, 모든 단어는 그래프 상의 경로가 존재해야 하며, 이 경로에 쓰여 있는 글자를 순서대로 적었을 때 단어와 일치해야 한다.
또한, 경로 상의 모든 정점은 아래와 같은 네 가지 조건을 만족해야 한다.
위의 조건은 경로는 첫 K개 글자에서 나누어질 수 있고, 마지막 K개 글자에서 만날 수 있음을 의미한다.
단어 N개가 주어진다. 이때, 정점의 수가 가장 적은 코코스를 구하는 프로그램을 작성하시오.
아래 그림은 예제를 정점의 수가 가장 적은 코코스로 나타낸 것이다.
아래 그래프는 위의 그래프보다 정점의 수가 적지만, 코코스가 아니다.
위의 그래프가 코코스가 아닌 이유는 4번째 글자 D에서 경로가 만나고, 6번째 글자 E에서 경로가 갈라져 문제의 조건을 만족하지 않기 때문이다.
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ 100)
다음 N개 줄에는 알파벳 대문자로만 이루어진 단어가 주어진다.
첫째 줄에 정점의 수가 가장 적은 코코스의 정점의 수를 출력한다.
2 4 ABCDEFGH EFGHIJKL
16
4 3 XXZZXX XXYYZZ AABBCZ ABCZZZ
18
4 4 ABCDEFGH ACBDEFGH ABDCFEHG EFEFFEGH
23
Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Croatian Olympiad in Informatics 2006 2번