모험가 길드 그리드

모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데 공포도가 높다면 대처능력이 떨어집니다. 모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명이상으로 구성한 모험가 그룹에 참석해야 여행을 떠날 수 있도록 규정했습니다. 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가가 주어졌을때 떠날 수 있는 그룹의 최댓값을 구하시오

대표적인 그리드 문제이다. 얼핏 생각해보아도 공포도가 제일 낮은 사람을 기준으로 정렬한 다음에 하나씩 빼면 되겠다.

num = int(input())
member = list(map(int, input().split()))

member.sort()

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

for i in member:
    #공포도를 낮은 것부터 하나씩 확인
    count += 1
    if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면 그룹 결성
        result += 1 #총 그룹의 수 증가시키기
        count = 0 #현재 그룹에 포함된 모험가의 수 초기화
print(result)

코드가 특별하지는 않다 for문 하나로 끝나는데 살펴보자

예시 입력

5

2 1 2 2 3

일단 count를 1에서 부터 시작해보자

첫번째 값은 1이 들어오고 1>=1 이므로 팀을 결성 할 수 있다. 최대그룹수를 1증가하고 count를 초기화한다.

두번째에서는 2가 들어오지만 1>=2 이므로 팀을 결성할 수 없다. 넘어간다.

세번째에서도 2가 들어온다. 그리고 카운트가 증가해서 2>=2 를 만족하여 팀을 결성할 수 있다. 다시 초기화한다.

그러면 남게 되는 것은 2와 3인데 결과적으로 이 둘은 팀을 이룰 수가 없다.

최종적인 결과는 2