비슷한 문자열
시간 제한1초메모리 제한1024 MB
길이가 K인 문자열 N개가 주어질 때, 남은 배열에서 이웃한 두 문자열이 같은 위치에서 같은 문자를 하나 이상 가지도록 최소 개수를 지운다.
문제
길이가 같은 두 문자열 와 가 비슷한 문자열이라는 것은 다음과 같이 정의된다.
- 인 모든 가운데 인 가 적어도 하나 존재한다.
길이가 인 문자열 개로 이루어진 배열이 있다. 이 배열에서 순서를 바꾸지 않고 0개 이상의 원소를 지워, 남은 배열의 모든 인접한 두 원소가 비슷한 문자열이 되도록 만들려고 한다. 지워야 하는 원소 개수의 최솟값을 구하시오.
입력
첫째 줄에 정수 , 가 공백을 사이에 두고 주어진다.
둘째 줄부터 개의 줄에 걸쳐 길이가 인 문자열이 한 줄에 하나씩 주어진다.
모든 문자열은 알파벳 소문자로만 구성되어 있다.
출력
첫째 줄에 정답을 출력한다.