시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 205 | 82 | 64 | 39.506% |
홍준이의 눈 앞에 N개의 색칠된 구슬이 놓여있다. 구슬의 색은 서로 다를 수 있다. 만약 같은 색의 구슬들이 K개 이상 연속되어 있으면 그 구슬들을 없앨 수 있다. 또한 구슬들을 없애는 작업을 미뤘다가 나중에 할 수도 있다. 운이 좋게도 홍준이에게는 구슬이 많이 있어 구슬들 사이에 원하는 색의 구슬을 끼워 넣을 수 있다. 물론, 맨 앞과 맨 뒤에도 놓을 수 있다.
홍준이를 도와 최소 개수의 구슬을 새로 끼워 넣어 모든 구슬을 없애는 프로그램을 작성하시오.
첫 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 2 ≤ K ≤ 5)
그리고 다음 줄에 놓여져 있는 구슬의 색이 차례대로 주어진다. 구슬의 색은 1이상 100이하의 자연수로 표현된다.
놓여져 있는 구슬을 모두 없애기 위해 새로 끼워 넣어야되는 구슬의 최소 개수를 출력한다.
2 5 1 1
3
5 3 2 2 3 2 2
2
10 4 3 3 3 3 2 3 1 1 1 3
4
Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #5 4번