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

모험가 길드

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

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

 

---

 

해답

 

n = int(input())

gongpo = list(map(int, input().split()))
gongpo.sort()

group, count = 0, 0

for i in gongpo:
    count = count + 1
    
    if i <= count:
        group = group + 1
        count = 0

print(group)

---

예시

 

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

---

해설

 

입력 n과 공포도 리스트 gongpo를 입력받습니다.
그리고 for 반복문으로 gongpo 리스트의 원소들을 하나하나 선택하고, 선택할 때 마다 count를 늘려줍니다.
count는 해당 그룹에서의 구성원 수 입니다.
만약 i보다 count가 크거나 같아진다면 그룹 개수에 해당하는 변수 group을 하나 늘려줍니다.
최종적으로 group을 출력해주면 됩니다.