모험가 길드 - 그리디

각 그룹을 최소한의 인원으로 짜면 최대의 그룹 수를 얻을 수 있다는 아이디어가 핵심이다.

조건에서 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 그룹에 들어가야 하고, 이러한 그룹을 최대한 많이 만들기 위해서는 공포도가 X인 사람은 딱 X명으로 구성된 그룹으로 묶어주는것이 좋겠다.

예시로 주어진 2, 3, 1, 2, 2  의 경우, 1 단 한명으로 구성된 그룹, 2 두명으로 이루어진 그룹으로 짜서 총 두개의 그룹을 만드는게 정답이 되는데, 모든 모험가가 그룹을 맺을 필요가 없으며 공포도가 큰 모험가 일수록 많은 인원을 필요로 하며, 결과적으로 비용이크므로 선호도가 떨어진다는 이야기가 된다는 사실에 기반하여 정답으로 판단 가능하다.

위 가정을 구현하기 위해 주어진 배열을 오름차순으로 정렬한 뒤 공포도에 따라 그룹으로 묶어주면 되겠다.

코드

n = int(input())
data = list(map(int,input().split()))
data.sort()

result = 0
count = 0

for i in data:
  count += 1
  if count >= i:
    result += 1
    count = 0

print(result)