구슬 없애기
시간 제한1초메모리 제한128 MB
구슬을 이어붙인 줄에서 같은 색이 K개 이상 연속되면 제거할 수 있을 때, 모든 구슬을 결국 제거할 수 있도록 삽입해야 하는 구슬의 최소 개수를 구합니다.
문제
홍준이 앞에 색칠된 구슬 N개가 한 줄로 놓여 있다. 구슬의 색은 서로 같을 수도, 다를 수도 있다. 같은 색 구슬이 K개 이상 연속으로 놓여 있으면, 그 연속된 구슬들을 한꺼번에 없앨 수 있다. 없애는 작업은 바로 하지 않고 나중으로 미룰 수도 있다.
홍준이는 여분의 구슬을 넉넉히 가지고 있어, 이미 놓인 구슬들 사이(맨 앞과 맨 뒤 포함)에 원하는 색의 구슬을 새로 끼워 넣을 수 있다.
새로 끼워 넣는 구슬의 개수를 최소로 하여 결국 모든 구슬을 없앨 수 있도록 할 때, 끼워 넣어야 하는 구슬의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 2 ≤ K ≤ 5)
둘째 줄에 놓여 있는 구슬의 색이 왼쪽부터 차례대로 주어진다. 각 구슬의 색은 1 이상 100 이하의 자연수로 표현된다.
출력
놓여 있는 모든 구슬을 없애기 위해 새로 끼워 넣어야 하는 구슬의 최소 개수를 출력한다.