시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB275581852332.364%

문제

남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다.

재혁: 동우가 안 가면 나도 안 간다.
동우: 세종이가 안 가면 난 안 갈래.

버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 많은 인원을 데려가지 않으면 안 되는 상황이었다.

각 사람이 원하는 같이 갈 사람이 주어질 때, 버스에 태울 수 있는 사람은 최대 몇 명인지 알아내시오.

입력

첫 번째 줄에 사람 수 n과 버스에 태울 수 있는 사람 수 k가 주어진다. (1 ≤ k ≤ n ≤ 1 000)

두 번째 줄에 n개의 정수 xi (i = 1, 2, ... , n, 1 ≤ xi ≤ n) 가 순서대로 주어진다. xi는 xi번째 사람이 버스에 타지 않는다면 i번째 사람 역시 버스에 타지 않음을 의미한다.

출력

모든 사람의 의견을 해치지 않고 최대한 태울 수 있는 인원수를 출력하시오.

예제 입력 1

4 4
1 2 3 4

예제 출력 1

4

예제 입력 2

12 3
2 3 4 5 6 7 4 7 8 8 12 12

예제 출력 2

2

예제 입력 3

5 4
2 3 1 5 4

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjEwMjY1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTVQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjBhOFx1YWRkY1x1YjI5NCBcdWIzZDlcdWFlMzBcdWI0ZTRcdWFjZmMgXHVjNWUwXHVkMmYwXHViOTdjJm5ic3A7XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjODRcdWMyYTRcdWI5N2MgXHViMzAwXHVjODA4XHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhY2ZjXHVjMGFjXHVjNzU4IFx1YzJlNFx1YzIxOFx1Yjg1YyZuYnNwO1x1YjMwMFx1YzgwOFx1YmM4NFx1YzJhNFx1Yzc1OCBcdWM3NzhcdWM2ZDBcdWM3NzQmbmJzcDtcdWM3OThcdWJhYmJcdWI0MThcdWM1YjQmbmJzcDtcdWIwYThcdWFkZGNcdWM3NTggXHViM2Q5XHVhZTMwXHViNGU0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQwZGNcdWM2YjgmbmJzcDtcdWMyMTggXHVjNWM2XHVjNWM4XHViMmU0LiBcdWM3NzQgXHVjNjQwXHVjOTExXHVjNWQwIFx1YjNkOVx1YWUzMFx1YjRlNFx1Yzc0MCBcdWQ2NTRcdWI5N2MgXHViMGI0XHViYTcwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViOWQwXHViNGU0XHVjNzQ0IFx1YzhmY1x1YWNlMFx1YmMxYlx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHVjN2FjXHVkNjAxOiBcdWIzZDlcdWM2YjBcdWFjMDAgXHVjNTQ4IFx1YWMwMFx1YmE3NCBcdWIwOThcdWIzYzQgXHVjNTQ4IFx1YWMwNFx1YjJlNC48YnIgXC8+XHJcblx1YjNkOVx1YzZiMDogXHVjMTM4XHVjODg1XHVjNzc0XHVhYzAwIFx1YzU0OCBcdWFjMDBcdWJhNzQgXHViMDljJm5ic3A7XHVjNTQ4IFx1YWMwOFx1Yjc5OC48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHViYzg0XHVjMmE0XHVjNWQwIFx1ZDBkY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc3OFx1YzZkMFx1YzIxOFx1YjI5NCBcdWQ1NWNcdWM4MTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwIFx1YmFhOFx1YjQ1MFx1YjRlNCBcdWIyZTRcdWI5NzggXHViMjA0XHVhZDcwXHVhYzAwXHVhYzAwIFx1YWMwMFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHVjNzkwXHVjMmUwXHViM2M0IFx1YWMwMFx1YzljMCBcdWM1NGFcdWFjYTBcdWIyZTQgXHVkNTU4XHViMmM4IFx1YjBhOFx1YWRkY1x1YjI5NCBcdWMyZTBcdWFjYmRcdWM3NzQgXHViZWQ3XHVjY2U0XHViMmU0LiBcdWFjOGNcdWIyZTRcdWFjMDAgXHVjMjIwXHVjNzQ0IFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NzQgXHVjMGMwXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1Yzc3OFx1YzZkMFx1Yzc0NCBcdWIzNzBcdWI4MjRcdWFjMDBcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YzU0OCBcdWI0MThcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWFjMTlcdWM3NzQgXHVhYzA4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJjODRcdWMyYTRcdWM1ZDAgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViYTg1XHVjNzc4XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1Yjc4YyBcdWMyMTggblx1YWNmYyBcdWJjODRcdWMyYTRcdWM1ZDAgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjIFx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IGsgJmxlOyBuICZsZTsgMSAwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHg8c3ViPmk8XC9zdWI+IChpID0gMSwgMiwgLi4uICwgbiwmbmJzcDsxICZsZTsgeDxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IG4pJm5ic3A7XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7eDxzdWI+aTxcL3N1Yj5cdWIyOTQgeDxzdWI+aTxcL3N1Yj5cdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHVjNzc0IFx1YmM4NFx1YzJhNFx1YzVkMCBcdWQwYzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IGlcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjIFx1YzVlZFx1YzJkYyBcdWJjODRcdWMyYTRcdWM1ZDAgXHVkMGMwXHVjOWMwIFx1YzU0YVx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwJm5ic3A7XHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc1OFx1YWNhY1x1Yzc0NCBcdWQ1NzRcdWNlNThcdWM5YzAgXHVjNTRhXHVhY2UwJm5ic3A7XHVjZDVjXHViMzAwXHVkNTVjIFx1ZDBkY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc3OFx1YzZkMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTAyNjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPdXRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL291dGluZy5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjY1cHg7IHdpZHRoOjI1MXB4XCIgXC8+T3JnYW5pc2luZyBhIGdyb3VwIHRyaXAgZm9yIHRoZSBlbGRlcmx5IGNhbiBiZSBhIGRhdW50aW5nIHRhc2suLi4gTm90IGxlYXN0IGJlY2F1c2Ugb2YgdGhlIGZ1c3N5IHBhcnRpY2lwYW50cywgZWFjaCBvZiB3aG9tIHdpbGwgb25seSBtYWtlIHRoZSB0cmlwIG9uIGNvbmRpdGlvbiB0aGF0IHNvbWUgb3RoZXIgcGFydGljaXBhbnQgYWxzbyBjb21lcy4gQWZ0ZXIgc29tZSBlZmZvcnQsIHlvdSBoYXZlIHRha2VuIGZyb20gZWFjaCBvZiB5b3VyIHBhcnRpY2lwYW50cyBhIG51bWJlciwgaW5kaWNhdGluZyB0aGF0IHRoaXMgcGFydGljaXBhbnQgd2lsbCByZWZ1c2UgdG8gam9pbiB0aGUgZXhjdXJzaW9uIHVubGVzcyB0aGUgcGFydGljaXBhbnQgd2l0aCB0aGF0IG51bWJlciBhbHNvIGpvaW5zJm5kYXNoOyB0aGUgbGVzcyBjaG9vc3kgc2ltcGx5IGdpdmUgdGhlaXIgb3duIG51bWJlci4gVGhpcyB3b3VsZCBiZSBlYXN5IGVub3VnaCB0byByZXNvbHZlIChqdXN0IHNlbmQgYWxsIG9mIHRoZW0pIGJ1dCB0aGUgYnVzIHlvdSBhcmUgZ29pbmcgdG8gdXNlIGR1cmluZyB0aGUgdHJpcCBoYXMgb25seSBhIGZpeGVkIG51bWJlciBvZiBwbGFjZXMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBwcmVmZXJlbmNlcyBvZiBhbGwgcGFydGljaXBhbnRzLCBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwYXJ0aWNpcGFudHMgdGhhdCBjYW4gam9pbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBrICgxICZsZTsgayAmbGU7IG4gJmxlOyAxIDAwMCksIHdoZXJlIG4gZGVub3RlcyB0aGUgdG90YWwgbnVtYmVyIG9mIHBhcnRpY2lwYW50cyBhbmQgayBkZW5vdGVzIHRoZSBudW1iZXIgb2YgcGxhY2VzIG9uIHRoZSBidXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGludGVnZXJzIHhpIGZvciBpID0gMSwgMiwgLi4uICwgbiwgd2hlcmUgMSAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgbi4gVGhlIG1lYW5pbmcgb2YgeDxzdWI+aTxcL3N1Yj4gaXMgdGhhdCB0aGUgaS10aCBwYXJ0aWNpcGFudCB3aWxsIHJlZnVzZSB0byBqb2luIHRoZSBleGN1cnNpb24gdW5sZXNzIHRoZSB4PHN1Yj5pPFwvc3ViPi10aCBwYXJ0aWNpcGFudCBhbHNvIGpvaW5zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlcjogdGhlIG1heGltdW0gbnVtYmVyIG9mIHBhcnRpY2lwYW50cyB0aGF0IGNhbiBqb2luIHRoZSBleGN1cnNpb24sIHNvIHRoYXQgYWxsIHRoZSBwYXJ0aWNpcGFudHMmcnNxdW87IHByZWZlcmVuY2VzIGFyZSBvYmV5ZWQgYW5kIHRoZSBjYXBhY2l0eSBvZiB0aGUgYnVzIGlzIG5vdCBleGNlZWRlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2014 G번

  • 문제를 번역한 사람: kks227
  • 문제를 만든 사람: Robin Lee