시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB205826439.506%

문제

홍준이의 눈 앞에 N개의 색칠된 구슬이 놓여있다. 구슬의 색은 서로 다를 수 있다. 만약 같은 색의 구슬들이 K개 이상 연속되어 있으면 그 구슬들을 없앨 수 있다. 또한 구슬들을 없애는 작업을 미뤘다가 나중에 할 수도 있다. 운이 좋게도 홍준이에게는 구슬이 많이 있어 구슬들 사이에 원하는 색의 구슬을 끼워 넣을 수 있다. 물론, 맨 앞과 맨 뒤에도 놓을 수 있다.

홍준이를 도와 최소 개수의 구슬을 새로 끼워 넣어 모든 구슬을 없애는 프로그램을 작성하시오.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 2 ≤ K ≤ 5)

그리고 다음 줄에 놓여져 있는 구슬의 색이 차례대로 주어진다. 구슬의 색은 1이상 100이하의 자연수로 표현된다.

출력

놓여져 있는 구슬을 모두 없애기 위해 새로 끼워 넣어야되는 구슬의 최소 개수를 출력한다.

예제 입력 1

2 5
1 1

예제 출력 1

3

예제 입력 2

5 3
2 2 3 2 2

예제 출력 2

2

예제 입력 3

10 4
3 3 3 3 2 3 1 1 1 3

예제 출력 3

4
W3sicHJvYmxlbV9pZCI6IjI4OTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWMyYWMgXHVjNWM2XHVjNTYwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWM3NTggXHViMjA4IFx1YzU1ZVx1YzVkMCZuYnNwO05cdWFjMWNcdWM3NTggXHVjMGM5XHVjZTYwXHViNDFjIFx1YWQ2Y1x1YzJhY1x1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzE5XHVjNzQwIFx1YzBjOVx1Yzc1OCBcdWFkNmNcdWMyYWNcdWI0ZTRcdWM3NzQgS1x1YWMxYyBcdWM3NzRcdWMwYzEgXHVjNWYwXHVjMThkXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFkZjggXHVhZDZjXHVjMmFjXHViNGU0XHVjNzQ0IFx1YzVjNlx1YzU2OCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVhZDZjXHVjMmFjXHViNGU0XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViYmY4XHViOTE4XHViMmU0XHVhYzAwIFx1YjA5OFx1YzkxMVx1YzVkMCBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNmI0XHVjNzc0IFx1Yzg4Ylx1YWM4Y1x1YjNjNCBcdWQ2NGRcdWM5MDBcdWM3NzRcdWM1ZDBcdWFjOGNcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzc0IFx1YjljZVx1Yzc3NCBcdWM3ODhcdWM1YjQgXHVhZDZjXHVjMmFjXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjMGM5XHVjNzU4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWIwN2NcdWM2Y2MgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Yjg2MCwgXHViOWU4IFx1YzU1ZVx1YWNmYyBcdWI5ZTggXHViNGE0XHVjNWQwXHViM2M0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHVhZDZjXHVjMmFjXHVjNzQ0IFx1YzBjOFx1Yjg1YyBcdWIwN2NcdWM2Y2MgXHViMTIzXHVjNWI0IFx1YmFhOFx1YjRlMCBcdWFkNmNcdWMyYWNcdWM3NDQgXHVjNWM2XHVjNTYwXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBOICZsZTsgMTAwLCAyJm5ic3A7JmxlOyBLJm5ic3A7JmxlOyA1KTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWM3NzQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZDZjXHVjMmFjXHVjNzU4IFx1YzBjOVx1Yzc0MCAxXHVjNzc0XHVjMGMxIDEwMFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM1YzZcdWM1NjBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzBjOFx1Yjg1YyBcdWIwN2NcdWM2Y2MgXHViMTIzXHVjNWI0XHVjNTdjXHViNDE4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODk5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWlVNQSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIGRheSBNaXJrbywgd2hpbGUgaGUgd2FzIHdhbGtpbmcgdGhyb3VnaCB0aGUgaGlnaCBncmFzcywgc3R1bWJsZWQgdXBvbiBhIHNlcXVlbmNlIG9mIE4gY29sb3JlZCBtYXJibGVzLiBTb29uIGhlIG5vdGljZWQgdGhhdCBpZiBoZSB0b3VjaGVzIEsgb3IgbW9yZSBjb25zZWN1dGl2ZSBtYXJibGVzIG9mIHRoZSBzYW1lIGNvbG9yLCB0aGV5IHN0YXJ0IHRvIHR3aW5rbGUgYW5kIHRoZW4gaGUgY291bGQgd2lzaCB0aGVtIHRvIG1hZ2ljYWxseSB2YW5pc2gsIGFsdGhvdWdoIGhlIGRvZXNuJiMzOTt0IGhhdmUgdG8gZG8gdGhhdCBpbW1lZGlhdGVseSAoc2VlIDMuIHNhbXBsZSkuIEZvcnR1bmF0ZWx5LCBNaXJrbyBicm91Z2h0IGFuIGluZXhoYXVzdGlibGUgc3VwcGx5IG9mIG1hcmJsZXMgZnJvbSBob21lLCBzbyBoZSBjYW4gaW5zZXJ0IGEgbWFyYmxlIG9mIGFueSBjb2xvciBhbnl3aGVyZSBpbiB0aGUgYXJyYXkgKGF0IHRoZSBiZWdpbm5pbmcsIGJldHdlZW4gYW55IHR3byBleGlzdGluZyBtYXJibGVzLCBvciBhdCB0aGUgZW5kKS4gSGVscCBNaXJrbyBmaW5kIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgbWFyYmxlcyBoZSBtdXN0IGluc2VydCBpbnRvIHRoZSBzZXF1ZW5jZSBiZWZvcmUgaGUgY291bGQgbWFrZSBhbGwgb2YgdGhlIG1hcmJsZXMgdmFuaXNoLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDEwMCkgYW5kIEsgKDIgJmxlOyBLICZsZTsgNSkgLSB0aGUgbnVtYmVyIG9mIG1hcmJsZXMgaW4gdGhlIGluaXRpYWwgc2VxdWVuY2UgYW5kIHRoZSBtaW5pbWFsIG51bWJlciBvZiBjb25zZWN1dGl2ZSBtYXJibGVzIG9mIHRoZSBzYW1lIGNvbG9yIGhlIGNvdWxkIHdpc2ggdG8gdmFuaXNoLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIGV4YWN0bHkgTiBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIDEwMCAoaW5jbHVzaXZlKSwgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZS4gVGhvc2UgbnVtYmVycyByZXByZXNlbnQgY29sb3JzIG9mIG1hcmJsZXMgaW4gdGhlIHNlcXVlbmNlIE1pcmtvIGZvdW5kLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9ubHkgb25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciAtIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtYXJibGVzIE1pcmtvIGhhcyB0byBpbnNlcnQgdG8gYWNoaXZlIHRoZSBkZXNpcmVkIGVmZmVjdC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #5 4번