[그리디] 모험가 길드

모험가 N 명이 있다. 모험가들은 각각의 공포도를 갖고 있다. 그래서 공포도가 X 인 모험가는 반드시 X 명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. 최대 몇개의 모험가 그룹을 만들수 있는가?

 

예를 들어 N이 5이고 각 모험가 공포도가 2 3 1 2 2 라고 해보자.

이때 group1(1 2 3), group2(2 2) 이렇게 두개의 그룹을 만들 수 있다. 그런데 문제의 조건이 더 있다. 몇명의 모험가들은 그룹에 포함되지 않아도 된다. 다시말해 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

 

이렇게 되면 group1(1), group2(2 2) 도 정답이 된다. 둘 다 답은 2로 같은데 group이 되는 과정이 달라서 헷갈렸다.

그리고 모험가들은 같은 공포도를 갖는다고 하더라도 개별적인 존재이니까 group2(2-1 2-2), group3(2-2 2-3), group4(2-3 2-1) 이렇게 봐야되지 않나라는 의문도 생겼다. 그런데 답은 심플했다. 오히려 많이 생각한게 문제풀이에 방해가 된거 같다.

 

결국 이문제도 전제가 필요하다. 공포도를 오름차순으로 정렬을 하면, 공포도가 낮은 순서대로 그룹이 만들어지게 되고 이는 가장 많은 그룹이 만들어진다는 게 보장된다.

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)

위 방식은 아까 예에서 group1(1), group2(2 2) 로 만들어지는 코드가 된다. 

 

 

 

 

 

 

출처 : 이것이 코딩테스트다. 나동빈저