모험가 길드 [그리디]

내 풀이

# 모험가 n명
# 공포도가 x인 모험가는 반드시 x명 이상으로 구성
# n명의 모험가 정보/ 여행 떠날 수 있는 그룹 최댓값
# 몇 명의 모험가는 마을에 남아있어도 됨

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

group=[]
count=0
result=0

for i in array:
    group.append(i)
    count+=1

    if max(group)<=count:
        group=[]
        count=0
        result+=1
    
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)
  • 나는 리스트를 하나 추가해서 쓸데없이 자원 낭비한 것 같다.
  • 1명도 그룹이 될 수 있다는 걸 모르고 헤맸음.

좋은 웹페이지 즐겨찾기