그리디 문제 : 모험가 길드 풀이

한 마을에 모험가가 n명. 공포도가 x인 모험가는 반드시 x명 이상으로 여행을 떠날 수 있다.

n명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성.

X는 각 공포도를 가지고 있는 모험가의 list 이다.

예를 들어서 N이 5이고, X가 [2 3 1 2 2]일 때 최댓값은 2임.

 

풀이 : 정렬을 해준 뒤 그룹에 모험가를 하나씩 추가해준다. (group을 1 증가 시킨다.)

그 뒤에 모험가의 공포도와 그룹의 수가 같다면 출발시킨다. (result를 1 증가 시킨다.)

n = int(input())
k = list(map(int,input().split()))

k.sort()

group = 0
result = 0

for i in k:
  group += 1

  if i <= group:
    result += 1
    group = 0

print(result)