해커톤

아이리포

[해커톤] 자유 코딩

작성자 : 아이리포 작성일 : 2021.07.22 14:07:00 댓글수 : 1 조회수 : 126

문제

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

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

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

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

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

입력

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

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

출력

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

첨부파일

  • 댓글을 입력 하시려면 로그인 해주세요.