[그리디] 기출 문제 (1) 모험가 길드 ✅

이코테 p.311 모험가 길드

입력 예시

5 2 3 1 2 2

출력 예시

2

소스코드

• 그룹 수를 최대화하려면 그룹 내 인원을 최소화해야 함
  • 공포도를 오름차순으로 정렬한 후, 가장 작은 공포도를 가진 사람부터 그룹 구성
• 현재의 공포도만큼 그룹에 사람 추가
  • 현재 그룹의 사람 수가 현재의 공포도보다 크거나 같아지면 그룹 수 +1 & 그룹 초기화

# 입력 받기
n = int(input())
array = list(map(int, input().split()))

# 오름차순으로 정렬
array.sort()

result = 0 # 총 그룹 수
count = 0 # 현재 그룹의 사람 수
for fear in result:
  count += 1 # 그룹에 사람 1명 추가
  if count >= fear: # 현재 그룹의 사람 수가 fear보다 크거나 같아지는 경우
    result += 1 # 그룹 수 1 증가
    count = 0 # 그룹 인원 초기화

print(result)