[그리디 알고리즘] ★ 문제3 - 모험가 길드

모험가 길드

---

---

1) 문제 해결 아이디어

오름차순 정렬 후 공포도가 낮은 모험가부터 확인한다.

 

(현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도) 일 때, 

현재 그룹핑 완료하기!

 

2) 소스 코드

n = int(input())    # 모험가 수
level = list(map(int, input().split()) ) # 공포도 리스트
level.sort()  # 공포도 오름차순 정렬

group = 0  # 그룹 수
humon = 0  # 현재 그룹에 포함된 모험가의 수

# 공포도 낮은 순부터 확인
for i in level:
  humon += 1  # 현재 그룹에 모험가 포함
  # 그룹 결성 조건(현재 공포도보다 그룹의 모험가 수가 크거나 같으면 그룹핑)
  if humon >= i:
    group += 1  # 그룹 수 증가
    humon = 0
print(group)