🔦 문제
모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로
구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라.
| 입력 | 출력 |
|---|---|
| 2 3 1 2 2 | 2 |
✍️ 풀이
공포도가 낮을 수록 그룹을 짜기 쉽기 때문에 오름차순으로 정렬을 해준다.
그 후 모든 모험가들을 차례대로 검사한다.
- 현재 모험가의 공포도가 그룹인원보다 높다면 그룹인원에 추가하고 다음 모험가를 탐색한다.
- 현재 모험가의 공포도가 그룹인원과 같다면 그룹과 여행을 떠난다.
그리고 다음 모험가를 탐색하며 새로운 그룹을 만든다.
이를 반복하면서 구하면 된다.
🛠 나의 코드
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
result = 0
count = 0
for i in range(len(arr)):
val = arr[i]
count += 1
if val == count:
result += 1
count = 0
print(result)
📝 정리
공포도가 오름차순으로 정렬되어 있기 때문에 현재 모험가의 공포도만 조사하면 최소한의 인원으로 그룹을 만들 수 있다.
따라서, 최대한의 그룹을 만들 수 있다.
🎈 참고
Go Go