시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 35 30 93.750%

문제

알버트가 다니는 학교에서 곧 해커톤이 열린다. 이 해커톤에는 N명의 학생이 참가 의사를 밝혔다. 편의상 학생에 번호를 매겼고, 번호는 1부터 N까지이다. 

해커톤에 참가하는 N명을 몇 개의 팀으로 나눠야 하는데, 대회 주최 측에서는 팀의 개수를 최소로 하고싶어 한다. 단, i번 학생은 자신이 속한 팀의 팀원 수가 자기 자신을 포함해서 Xi명 이하일 때만 참가한다고 한다. 주최 측은 참가 의사를 밝힌 N명이 모두 참여할 수 있도록 팀을 배정할 생각이며, 이 때 팀의 수를 최소로 하려고 한다.

다음 조건을 모두 만족하게 팀을 만들어야 한다.

  • 한 학생은 하나의 팀에 소속되어야 한다.
  • 각 팀은 최소 한 명의 학생을 포함한다.
  • 모든 i에 대해서, i번 학생이 속한 팀의 팀원 수는 Xi명 이하이어야 한다.

위의 조건을 만족하면서 N명을 팀으로 나눴을 때, 팀의 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 학생의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 N개의 정수가 주어지고, 순서대로 X1, X2, ..., XN을 의미한다. 모든 i에 대해서, 1 ≤ Xi ≤ N을 만족한다.

출력

첫째 줄에 팀의 수의 최솟값을 출력한다.

예제 입력 1

2
2 2

예제 출력 1

1

예제 입력 2

5
1 2 5 2 1

예제 출력 2

4

예제 입력 3

5
1 2 1 2 1

예제 출력 3

4

예제 입력 4

9
2 2 2 3 3 3 2 2 2

예제 출력 4

4

다음과 같이 4팀을 만들 수 있다.

{1, 9}, {2, 8}, {3, 7}, {4, 5, 6}

예제 입력 5

9
2 2 2 2 2 3 3 3 3

예제 출력 5

4

다음과 같이 4팀을 만들 수 있다.

{1, 2}, {3, 4}, {5, 6}, {7, 8, 9}

힌트

예를 들어, 5명의 학생이 있고, X1 = 1, X2 = 2, X3 = 5, X4 = 2, X5 = 1인 경우에 팀의 수의 최솟값은 4이다.

{1}, {2}, {3}, {4}, {5}로 5개의 팀을 만드는 방법이 있지만, 이것은 팀의 수가 최소가 아니다. {1}, {3}, {5}, {2, 4}와 같이 팀을 만들면, 문제의 조건을 모두 만족하고, 팀의 수도 최소이다.

W3sicHJvYmxlbV9pZCI6IjE2MjAwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTc0XHVjZWU0XHVkMWE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWJjODRcdWQyYjhcdWFjMDAgXHViMmU0XHViMmM4XHViMjk0IFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyBcdWFjZTcgXHVkNTc0XHVjZWU0XHVkMWE0XHVjNzc0IFx1YzVmNFx1YjliMFx1YjJlNC4gXHVjNzc0IFx1ZDU3NFx1Y2VlNFx1ZDFhNFx1YzVkMFx1YjI5NCBOXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWNjMzhcdWFjMDAgXHVjNzU4XHVjMGFjXHViOTdjIFx1YmMxZFx1ZDYxNFx1YjJlNC4mbmJzcDtcdWQzYjhcdWM3NThcdWMwYzEgXHVkNTU5XHVjMGRkXHVjNWQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI5ZTRcdWFjYmNcdWFjZTAsIFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDU3NFx1Y2VlNFx1ZDFhNFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWIyOTQgTlx1YmE4NVx1Yzc0NCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1ZDMwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMjBcdWM1N2MgXHVkNTU4XHViMjk0XHViMzcwLCBcdWIzMDBcdWQ2OGMgXHVjOGZjXHVjZDVjIFx1Y2UyMVx1YzVkMFx1YzExY1x1YjI5NCBcdWQzMDBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWFjZTBcdWMyZjZcdWM1YjQgXHVkNTVjXHViMmU0LiBcdWIyZTgsIGlcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMxOGRcdWQ1NWMgXHVkMzAwXHVjNzU4IFx1ZDMwMFx1YzZkMCBcdWMyMThcdWFjMDAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NzRcdWMxMWMgWDxzdWI+aTxcL3N1Yj5cdWJhODUgXHVjNzc0XHVkNTU4XHVjNzdjIFx1YjU0Y1x1YjljYyBcdWNjMzhcdWFjMDBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4ZmNcdWNkNWMgXHVjZTIxXHVjNzQwIFx1Y2MzOFx1YWMwMCBcdWM3NThcdWMwYWNcdWI5N2MgXHViYzFkXHVkNzhjIE5cdWJhODVcdWM3NzQgXHViYWE4XHViNDUwIFx1Y2MzOFx1YzVlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDMwMFx1Yzc0NCBcdWJjMzBcdWM4MTVcdWQ1NjAgXHVjMGRkXHVhYzAxXHVjNzc0XHViYTcwLCBcdWM3NzQgXHViNTRjIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWQ1NWMgXHVkNTU5XHVjMGRkXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQzMDBcdWM1ZDAgXHVjMThjXHVjMThkXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1ZDMwMFx1Yzc0MCBcdWNkNWNcdWMxOGMgXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgaVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIGlcdWJjODggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzE4ZFx1ZDU1YyBcdWQzMDBcdWM3NTggXHVkMzAwXHVjNmQwIFx1YzIxOFx1YjI5NCBYPHN1Yj5pPFwvc3ViPlx1YmE4NSBcdWM3NzRcdWQ1NThcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIE5cdWJhODVcdWM3NDQgXHVkMzAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIzNFx1Yzc0NCBcdWI1NGMsIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgWDxzdWI+MTxcL3N1Yj4sIFg8c3ViPjI8XC9zdWI+LCAuLi4sIFg8c3ViPk48XC9zdWI+XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIGlcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCAxICZsZTsgWDxzdWI+aTxcL3N1Yj4gJmxlOyBOXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNVx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNzg4XHVhY2UwLCBYPHN1Yj4xPFwvc3ViPiA9IDEsIFg8c3ViPjI8XC9zdWI+ID0gMiwgWDxzdWI+MzxcL3N1Yj4gPSA1LCBYPHN1Yj40PFwvc3ViPiA9IDIsIFg8c3ViPjU8XC9zdWI+ID0gMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkMzAwXHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDAgNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+ezF9LCB7Mn0sIHszfSwgezR9LCB7NX1cdWI4NWMgNVx1YWMxY1x1Yzc1OCBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWQzMDBcdWM3NTggXHVjMjE4XHVhYzAwJm5ic3A7XHVjZDVjXHVjMThjXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC4gezF9LCB7M30sIHs1fSwgezIsIDR9XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGU0XHViYTc0LCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjZTAsIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWIzYzQgXHVjZDVjXHVjMThjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0Iiwic2FtcGxlX2V4cGxhaW5fNCI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgNFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+ezEsIDl9LCB7MiwgOH0sIHszLCA3fSwgezQsIDUsIDZ9PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fNSI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgNFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+ezEsIDJ9LCB7MywgNH0sIHs1LCA2fSwgezcsIDgsIDl9PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTYyMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUZWFtIEZvcm1hdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+QWxiZXJ0JiMzOTtzIHNjaG9vbCBpcyBob3N0aW5nIGEgaGFja2F0aG9uIGV2ZW50IGZvciBzdHVkZW50cy4gVGhlcmUgYXJlIE4gc3R1ZGVudHMgd2hvIHdpc2ggdG8gcGFydGljaXBhdGUgaW4gdGhlIGV2ZW50LiBMZXQmIzM5O3MgbGFiZWwgdGhlIHN0dWRlbnRzIGFzIDEsIDIsIC4uLiwgTi48XC9wPlxyXG5cclxuPHA+U3R1ZGVudCBpIHdhbnRzIHRvIHBhcnRpY2lwYXRlIGluIHRoZSBldmVudCZuYnNwO2lmIGFuZCBvbmx5IGlmIHRoZSB0ZWFtIGhlXC9zaGUgYmVsb25ncyB0byBoYXMgYXQgbW9zdCBYPHN1Yj5pPFwvc3ViPiBtZW1iZXJzIGluIGl0IChpbmNsdWRpbmcgc3R1ZGVudCBpKS4gQmVjYXVzZSB0aGUgc3BhY2UgaXMgbGltaXRlZCBhdCB0aGUgZXZlbnQgdmVudWUsIHRoZSBzY2hvb2wgbmVlZHMgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiB0ZWFtcy4gTW9yZSBwcmVjaXNlbHksIEFsYmVydCB3YW50cyB0byBjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0ZWFtcyB3aGlsZSBtZWV0aW5nIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5FdmVyeSBzdHVkZW50IGlzIGFzc2lnbmVkIHRvIGV4YWN0bHkgb25lIHRlYW08XC9saT5cclxuXHQ8bGk+RWFjaCB0ZWFtIGNvbnRhaW5zIGF0IGxlYXN0IG9uZSBzdHVkZW50PFwvbGk+XHJcblx0PGxpPklmIHN0dWRlbnQgaSBiZWxvbmdzIHRvIGEgdGVhbSwgdGhlbiB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzIGluIHRoZSB0ZWFtIChpbmNsdWRpbmcgc3R1ZGVudCBpKSBpcyBubyBncmVhdGVyIHRoYW4gWDxzdWI+aTxcL3N1Yj4uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxiZXJ0IG5lZWRzIHRvIGhlbHAgaGlzIHNjaG9vbCBob3N0IHRoZSBldmVudCBzdWNjZXNzZnVsbHksIGFuZCB5b3UgbmVlZCB0byBoZWxwIEFsYmVydCBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRlYW1zIHRoYXQgY2FuIGJlIGZvcm1lZCBnaXZlbiBzdHVkZW50cyYjMzk7IGNvbnN0cmFpbnRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMsIE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSB3aWxsIGNvbnRhaW4gTiBpbnRlZ2VycyByZXByZXNlbnRpbmcgWDxzdWI+aTxcL3N1Yj4gdmFsdWVzIGZvciBlYWNoIHN0dWRlbnQuIEFzc3VtZSB0aGF0IDEgJmxlOyZuYnNwO1g8c3ViPmk8XC9zdWI+ICZsZTsmbmJzcDtOIGZvciBhbGwgaSYjMzk7cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3Ugc2hvdWxkIG91dHB1dCBhIHNpbmdsZSBudW1iZXIsIHJlcHJlc2VudGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgdGVhbXMgdGhhdCBjYW4gYmUgZm9ybWVkLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgaW5zdGFuY2UsIHN1cHBvc2UgdGhlcmUgYXJlIGZpdmUgc3R1ZGVudHMgKE4gPSA1KSB3aXRoIFg8c3ViPjE8XC9zdWI+ID0gMSwgWDxzdWI+MjxcL3N1Yj4gPSAyLCBYPHN1Yj4zPFwvc3ViPiA9IDUsIFg8c3ViPjQ8XC9zdWI+ID0gMiwgYW5kIFg8c3ViPjU8XC9zdWI+ID0gMS4gSW4gcGFydGljdWxhciwgc3R1ZGVudCAzIHdpc2hlcyB0byBiZSBpbiBhIHRlYW0gd2l0aCBhdCBtb3N0IDUgbWVtYmVycywgd2hlcmVhcyBzdHVkZW50cyAyIGFuZCA0IGF0IG1vc3QgMiBzdHVkZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T25lICh0cml2aWFsKSB3YXkgdG8gZm9ybSB0ZWFtcyBpcyB0byBsZXQgZWFjaCBzdHVkZW50IGZvcm0gYSAxLXBlcnNvbiB0ZWFtIC0tIHRoaXMgeWllbGRzIGZpdmUgdGVhbXMuIE9yLCB3ZSBjYW4gbGV0IHN0dWRlbnRzIDIgYW5kIDQgZm9ybSBvbmUgdGVhbSwgYW5kIHRoZSBvdGhlciB0aHJlZSBzdHVkZW50cyBmb3JtIDEtcGVyc29uIHRlYW1zIC0tIHRoaXMgcmVzdWx0cyBpbiBmb3VyIHRlYW1zLiBJbiB0aGlzIGV4YW1wbGUsIHRoZXJlIGlzIG5vIHdheSB0byBmb3JtIDMgb3IgZmV3ZXIgdGVhbXMgd2hpbGUgbWVldGluZyB0aGUgc2FpZCBjb25kaXRpb25zLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0Iiwic2FtcGxlX2V4cGxhaW5fNCI6IjxwPkhlcmUgaXMgb25lIHNvbHV0aW9uIHRvIGFzc2lnbiBzdHVkZW50cyB0byBmb3VyIHRlYW1zOjxcL3A+XHJcblxyXG48cD57MSwgOX0sIHsyLCA4fSwgezMsIDd9LCB7NCwgNSwgNn0uPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fNSI6IjxwPkhlcmUgaXMgb25lIHNvbHV0aW9uIHRvIGFzc2lnbiBzdHVkZW50cyB0byBmb3VyIHRlYW1zOjxcL3A+XHJcblxyXG48cD57MSwgMn0sIHszLCA0fSwgezUsIDZ9LCB7NywgOCwgOX0uPFwvcD5cclxuIn1d

출처

  • 문제를 만든 사람: haden
  • 잘못된 데이터를 찾은 사람: tncks0121