시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1034 412 307 41.430%

문제

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

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

공항에는 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+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVhY2Y1XHVkNTZkXHVjNzQ0IFx1YzZiNFx1YzYwMVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHVhYzA0XHVkNjM5IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVhY2YzXHVjNWQwXHViM2M0IFx1YjNjNFx1ZDBiOVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMGFjXHVhY2UwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzBhY1x1YWNlMFx1YWMwMCBcdWM3N2NcdWM1YjRcdWIwOThcdWJhNzQgXHVhY2Y1XHVkNTZkXHVjNzU4IFx1ZDNjOVx1ZDMxMFx1Yzc3NCBcdWFlMDlcdWMxOGRcdWQ3ODggXHViMDk4XHViZTYwXHVjODM4LCBcdWM3NzRcdWQ2YzQgXHVjNWI0XHViNWE0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YjNjNCBcdWIzYzRcdWNjMjlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViODI0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1YzJiOVx1YzZkMFx1Yzc0MCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWFjZjVcdWQ1NmRcdWM1ZDAgXHViM2M0XHVkMGI5XHVjMmRjXHVjZjFjXHVjMTFjIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc0NCBcdWQ1ODlcdWJjZjVcdWQ1NThcdWFjOGMgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YjMwMCBcdWIzYzRcdWQwYjlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YWMwMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1YzIxOCBHICgxICZsZTsgRyAmbGU7IDEwPHN1cD41PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yzc1OCBcdWMyMTggUCAoMSAmbGU7IFAgJmxlOyAxMDxzdXA+NTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGc8c3ViPmk8XC9zdWI+ICgxICZsZTsgZzxzdWI+aTxcL3N1Yj4gJmxlOyBHKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzJiOVx1YzZkMFx1Yzc3NFx1YWMwMCBcdWIzYzRcdWQwYjlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDBcdWM3NTggXHViZTQ0XHVkNTg5XHVhZTMwIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyAxIDogWzJdWz9dWz9dWzFdIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWIzYzRcdWQwYjlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gM1x1YmM4OFx1YzlmOCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWIyOTQgXHViM2M0XHVkMGI5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxYyAyIDogWzFdWzJdWzNdWz9dIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWIzYzRcdWQwYjkgXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIDRcdWJjODhcdWM5ZjggXHViZTQ0XHVkNTg5XHVhZTMwXHViMjk0IFx1YzgwOFx1YjMwMCBcdWIzYzRcdWQwYjkgXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM1YzZcdWM1YjRcdWMxMWMgXHVjNzc0XHVkNmM0IFx1Y2Q5NFx1YWMwMFx1YzgwMVx1Yzc3OCBcdWIzYzRcdWQwYjlcdWM3NDAgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNzc1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2F0ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkZvciB5b3VyIGJpcnRoZGF5LCB5b3Ugd2VyZSBnaXZlbiBhbiBhaXJwb3J0LjxcL3A+XHJcblxyXG48cD5UaGUgYWlycG9ydCBoYXMgRyBnYXRlcywgbnVtYmVyZWQgZnJvbSAxIHRvIEcuPFwvcD5cclxuXHJcbjxwPlAgcGxhbmVzIGFycml2ZSBhdCB0aGUgYWlycG9ydCwgb25lIGFmdGVyIGFub3RoZXIuIFlvdSBhcmUgdG8gYXNzaWduIHRoZSBpdGggcGxhbmUgdG8gcGVybWFuZW50bHkgZG9jayBhdCBhbnkgZ2F0ZSAxLCAuIC4gLiAsIGc8c3ViPmk8XC9zdWI+ICgxICZsZTsgZzxzdWI+aTxcL3N1Yj4gJmxlOyBHKSwgYXQgd2hpY2ggbm8gcHJldmlvdXMgcGxhbmUgaGFzIGRvY2tlZC4gQXMgc29vbiBhcyBhIHBsYW5lIGNhbm5vdCBkb2NrIGF0IGFueSBnYXRlLCB0aGUgYWlycG9ydCBpcyBzaHV0IGRvd24gYW5kIG5vIGZ1dHVyZSBwbGFuZXMgYXJlIGFsbG93ZWQgdG8gYXJyaXZlLjxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBrZWVwIHRoZSBwZXJzb24gd2hvIGdhdmUgeW91IHRoZSBhaXJwb3J0IGhhcHB5LCB5b3Ugd291bGQgbGlrZSB0byBtYXhpbWl6ZSB0aGUgbnVtYmVyIG9mIHBsYW5lcyBzdGFydGluZyBmcm9tIHRoZSBiZWdpbm5pbmcgdGhhdCBjYW4gYWxsIGRvY2sgYXQgZGlmZmVyZW50IGdhdGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgRyAoMSAmbGU7IEcgJmxlOyAxMDxzdXA+NTxcL3N1cD4pLCB0aGUgbnVtYmVyIG9mIGdhdGVzIGF0IHRoZSBhaXJwb3J0LjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgUCAoMSAmbGU7IFAgJmxlOyAxMDxzdXA+NTxcL3N1cD4pLCB0aGUgbnVtYmVyIG9mIHBsYW5lcyB3aGljaCB3aWxsIGxhbmQuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IFAgbGluZXMgY29udGFpbiBvbmUgaW50ZWdlciBnPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGc8c3ViPmk8XC9zdWI+ICZsZTsgRyksIHN1Y2ggdGhhdCB0aGUgaXRoIHBsYW5lIG11c3QgZG9jayBhdCBzb21lIGdhdGUgZnJvbSAxIHRvIGc8c3ViPmk8XC9zdWI+LCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCBmb3IgYXQgbGVhc3QgNDAlIG9mIHRoZSBtYXJrcyBmb3IgdGhpcyBxdWVzdGlvbiwgUCAmbGU7IDIwMDAgYW5kIEcgJmxlOyAyMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGxhbmVzIHRoYXQgY2FuIGxhbmQgc3RhcnRpbmcgZnJvbSB0aGUgYmVnaW5uaW5nLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5FeHBsYW5hdGlvbiBvZiBPdXRwdXQgZm9yIFNhbXBsZSBJbnB1dCAxPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBwbGFuZSBjYW4gZ28gYW55d2hlcmUsIGJ1dCBpdCBpcyBiZXN0IHRvIG5vdCBwdXQgaXQgaW50byBHYXRlIDEuIE5vdGljZSB0aGF0IHBsYW5lcyAyIGFuZCAzIGJvdGggd2FudCB0byBkb2NrIGludG8gR2F0ZSAxLCBzbyBwbGFuZSAzIGlzIHVuYWJsZSB0byBkb2NrLjxcL3A+XHJcblxyXG48cD5FeHBsYW5hdGlvbiBvZiBPdXRwdXQgZm9yIFNhbXBsZSBJbnB1dCAyPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCB0d28gcGxhbmVzIHdpbGwgZG9jayBpbiBnYXRlcyAxIGFuZCAyIChpbiBhbnkgb3JkZXIpLiBUaGUgdGhpcmQgcGxhbmUgbXVzdCBkb2NrIGF0IEdhdGUgMy4gVGh1cywgdGhlIGZvdXJ0aCBwbGFuZSBjYW5ub3QgZG9jayBhbnl3aGVyZSwgYW5kIHRoZSBhaXJwb3J0IGlzIGNsb3NlZCwgZXZlbiB0aG91Z2ggcGxhbmUgNSB3b3VsZCBoYXZlIGJlZW4gYWJsZSB0byBkb2NrLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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