[그리디 알고리즘] 모험가 길드 - 파이썬(python)

모험가 길드

난이도 : 下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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

count, result = 0, 0

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

print(result)

---

예시

 

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) # 총 그룹의 수 출력

---

해설

 

공포도를 오름차순으로 정렬한 뒤, 차례대로 그룹에 포함시키면 되는 문제입니다.
count가 i 이상이라면 result를 증가시킨다는 아이디어만 떠올리면 쉽게 해결할 수 있습니다.