시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1240 492 371 40.994%

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

힌트

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.

예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불가능하다.

 

W3sicHJvYmxlbV9pZCI6IjEwNzc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2Y1XHVkNTZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWI5ZGVcdWM1NDQgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNWQwXHVhYzhjIFx1Yzc3OFx1Y2M5Y1x1YWQ2ZFx1YzgxY1x1YWNmNVx1ZDU2ZFx1Yzc0NCBcdWMxMjBcdWJiM2NcdWI4NWMgXHVjOTJjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWQ1NmRcdWM1ZDBcdWIyOTQgR1x1YWMxY1x1Yzc1OCBcdWFjOGNcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMVx1YWMwMVx1Yzc0MCAxXHVjNWQwXHVjMTFjIEdcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmNVx1ZDU2ZFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViM2M0XHVjYzI5XHVkNTYwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YmE3MCwgXHViMmY5XHVjMmUwXHVjNzQwIGlcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIDFcdWJjODhcdWJkODBcdWQxMzAgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpIFx1YmM4OFx1YzlmOCBcdWFjOGNcdWM3NzRcdWQyYjhcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwIFx1YzYwMVx1YWQ2Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWIzYzRcdWQwYjlcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWJlNDRcdWQ1ODlcdWFlMzBcdWFjMDAgXHViM2M0XHVkMGI5XHViNDFjIFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YzVkMFx1YjI5NCBcdWIyZTRcdWI5NzggXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVhY2Y1XHVkNTZkXHVjNzQ0IFx1YzZiNFx1YzYwMVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHVhYzA0XHVkNjM5IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVhY2YzXHVjNWQwXHViM2M0IFx1YjNjNFx1ZDBiOVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMGFjXHVhY2UwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzBhY1x1YWNlMFx1YWMwMCBcdWM3N2NcdWM1YjRcdWIwOThcdWJhNzQgXHVhY2Y1XHVkNTZkXHVjNzU4IFx1ZDNjOVx1ZDMxMFx1Yzc3NCBcdWFlMDlcdWMxOGRcdWQ3ODggXHViMDk4XHViZTYwXHVjODM4LCBcdWM3NzRcdWQ2YzQgXHVjNWI0XHViNWE0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjNjNCBcdWIzYzRcdWNjMjlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViODI0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1YzJiOVx1YzZkMFx1Yzc0MCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWFjZjVcdWQ1NmRcdWM1ZDAgXHViM2M0XHVkMGI5XHVjMmRjXHVjZjFjXHVjMTFjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc0NCBcdWQ1ODlcdWJjZjVcdWQ1NThcdWFjOGMgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YjMwMCBcdWIzYzRcdWQwYjlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YWMwMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWMyMTggRyAoMSAmbGU7IEcgJmxlOyAxMDxzdXA+NTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHVjNzU4IFx1YzIxOCBQICgxICZsZTsgUCAmbGU7IDEwPHN1cD41PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgUFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMmI5XHVjNmQwXHVjNzc0XHVhYzAwIFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWJlNDRcdWQ1ODlcdWFlMzAgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIDEgOiBbMl1bP11bP11bMV0gXHVkNjE1XHVkMGRjXHViODVjIFx1YjNjNFx1ZDBiOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiAzXHViYzg4XHVjOWY4IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjI5NCBcdWIzYzRcdWQwYjlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIDIgOiBbMV1bMl1bM11bP10gXHVkNjE1XHVkMGRjXHViODVjIFx1YjNjNFx1ZDBiOSBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgNFx1YmM4OFx1YzlmOCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWIyOTQgXHVjODA4XHViMzAwIFx1YjNjNFx1ZDBiOSBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1YzVjNlx1YzViNFx1YzExYyBcdWM3NzRcdWQ2YzQgXHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YjNjNFx1ZDBiOVx1Yzc0MCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA3NzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYXRlcyIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIHlvdXIgYmlydGhkYXksIHlvdSB3ZXJlIGdpdmVuIGFuIGFpcnBvcnQuPFwvcD5cclxuXHJcbjxwPlRoZSBhaXJwb3J0IGhhcyBHIGdhdGVzLCBudW1iZXJlZCBmcm9tIDEgdG8gRy48XC9wPlxyXG5cclxuPHA+UCBwbGFuZXMgYXJyaXZlIGF0IHRoZSBhaXJwb3J0LCBvbmUgYWZ0ZXIgYW5vdGhlci4gWW91IGFyZSB0byBhc3NpZ24gdGhlIGl0aCBwbGFuZSB0byBwZXJtYW5lbnRseSBkb2NrIGF0IGFueSBnYXRlIDEsIC4gLiAuICwgZzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBnPHN1Yj5pPFwvc3ViPiAmbGU7IEcpLCBhdCB3aGljaCBubyBwcmV2aW91cyBwbGFuZSBoYXMgZG9ja2VkLiBBcyBzb29uIGFzIGEgcGxhbmUgY2Fubm90IGRvY2sgYXQgYW55IGdhdGUsIHRoZSBhaXJwb3J0IGlzIHNodXQgZG93biBhbmQgbm8gZnV0dXJlIHBsYW5lcyBhcmUgYWxsb3dlZCB0byBhcnJpdmUuPFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGtlZXAgdGhlIHBlcnNvbiB3aG8gZ2F2ZSB5b3UgdGhlIGFpcnBvcnQgaGFwcHksIHlvdSB3b3VsZCBsaWtlIHRvIG1heGltaXplIHRoZSBudW1iZXIgb2YgcGxhbmVzIHN0YXJ0aW5nIGZyb20gdGhlIGJlZ2lubmluZyB0aGF0IGNhbiBhbGwgZG9jayBhdCBkaWZmZXJlbnQgZ2F0ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBHICgxICZsZTsgRyAmbGU7IDEwPHN1cD41PFwvc3VwPiksIHRoZSBudW1iZXIgb2YgZ2F0ZXMgYXQgdGhlIGFpcnBvcnQuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBQICgxICZsZTsgUCAmbGU7IDEwPHN1cD41PFwvc3VwPiksIHRoZSBudW1iZXIgb2YgcGxhbmVzIHdoaWNoIHdpbGwgbGFuZC48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgUCBsaW5lcyBjb250YWluIG9uZSBpbnRlZ2VyIGc8c3ViPmk8XC9zdWI+ICgxICZsZTsgZzxzdWI+aTxcL3N1Yj4gJmxlOyBHKSwgc3VjaCB0aGF0IHRoZSBpdGggcGxhbmUgbXVzdCBkb2NrIGF0IHNvbWUgZ2F0ZSBmcm9tIDEgdG8gZzxzdWI+aTxcL3N1Yj4sIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IGZvciBhdCBsZWFzdCA0MCUgb2YgdGhlIG1hcmtzIGZvciB0aGlzIHF1ZXN0aW9uLCBQICZsZTsgMjAwMCBhbmQgRyAmbGU7IDIwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIG51bWJlciBvZiBwbGFuZXMgdGhhdCBjYW4gbGFuZCBzdGFydGluZyBmcm9tIHRoZSBiZWdpbm5pbmcuPFwvcD5cclxuIiwiaGludCI6IjxwPkV4cGxhbmF0aW9uIG9mIE91dHB1dCBmb3IgU2FtcGxlIElucHV0IDE8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IHBsYW5lIGNhbiBnbyBhbnl3aGVyZSwgYnV0IGl0IGlzIGJlc3QgdG8gbm90IHB1dCBpdCBpbnRvIEdhdGUgMS4gTm90aWNlIHRoYXQgcGxhbmVzIDIgYW5kIDMgYm90aCB3YW50IHRvIGRvY2sgaW50byBHYXRlIDEsIHNvIHBsYW5lIDMgaXMgdW5hYmxlIHRvIGRvY2suPFwvcD5cclxuXHJcbjxwPkV4cGxhbmF0aW9uIG9mIE91dHB1dCBmb3IgU2FtcGxlIElucHV0IDI8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IHR3byBwbGFuZXMgd2lsbCBkb2NrIGluIGdhdGVzIDEgYW5kIDIgKGluIGFueSBvcmRlcikuIFRoZSB0aGlyZCBwbGFuZSBtdXN0IGRvY2sgYXQgR2F0ZSAzLiBUaHVzLCB0aGUgZm91cnRoIHBsYW5lIGNhbm5vdCBkb2NrIGFueXdoZXJlLCBhbmQgdGhlIGFpcnBvcnQgaXMgY2xvc2VkLCBldmVuIHRob3VnaCBwbGFuZSA1IHdvdWxkIGhhdmUgYmVlbiBhYmxlIHRvIGRvY2suPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Canadian Computing Competition & Olympiad > 2015 > CCC 2015 Senior Division 3번

  • 데이터를 추가한 사람: chan4928
  • 문제를 번역한 사람: koosaga