[Python] 그리디 알고리즘을 파헤쳐 보자! (모험가 길드)

문제

• 한 마을에 모험가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대터할 능력이 떨어집니다.
• 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁급합니다. N명의 모험가에 대한 정보가 주어졌을 떄, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
• 단, 모든 모험가가 그룹에 참여하지 않아도 됩니다.

입력

5
2 3 1 2 2

첫째 줄에는 모험가 N명을 입력합니다.

둘째 줄에는 모험가 N명의 공포도를 입력합니다.

출력

2

정답

import sys

n = int(sys.stdin.readline().strip())
data = list(map(int, sys.stdin.readline().strip().split()))
# data 오름차순 정렬
data.sort()

# 총 그룹의 수 (최댓값)
result = 0
# 현재 그룹에 포함된 모험가의 수
cnt = 0

for i in data:
    cnt += 1
	
    # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면
    if cnt >= i:
        result += 1
        cnt = 0

print(result)

Tip

이번 해결법은 가장 적은 공포도를 가진 모험가부터 그룹을 결성하는 것이 많은 그룹을 결성하는 방법이다.

그러므로 정렬 메소드인 sort를 사용하여 공포도를 오름차순 만들어 차근차근 확인하는 것이 좋다.

 

sort()

# data = [2, 3, 1, 2, 2]
data.sort()
# data = [1, 2, 2, 2, 3]

"""
	reverse Default 값 = False
    
	오름차순 정렬
	data.sort(False)
    
	내림차순 정렬
	data.sort(True)
"""

참고

본 문제와 풀이는 해당 영상을 참고하여 만들었습니다.