▶ 문제 설명
- 한 마을에 모험가가 N명 있습니다.
- 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.
- 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
- 동빈이는 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다.
- 동빈이를 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
- 예를 들어 N=5이고, 각 모험가의 공포도가 다음과 같다고 가정합시다.
- 이때 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면, 총 2개의 그룹을 만들 수 있습니다.
- 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.
▶ 입력 조건
- 첫째 줄에 모험가의 수 N이 주어집니다. (1<=N<=100,000)
- 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.
▶출력 조건
- 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.
▶ Code
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) # 총 그룹의 수 출력
▶ Point
- 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인합니다.
- 앞에서부터 공포도를 하나씩 확인하며 '현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도' 보다 크거나 같다면 이를 그룹으로 설정하면 됩니다.
- 이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됩니다.
- 최대한 많은 그룹 수를 만드는 방법은, 최소한의 인원으로만 그룹을 구성하는 것이다.
- 모든 모험가들이 전부 그룹화 될 필요는 없으므로, 그룹 결성이 가능한 모험가들로만 그룹을 결성하면 된다.
- 따라서, 모험가들의 공포도를 오름차순 정렬한 뒤 순서대로 탐색하며, 그룹 결성이 가능한 최소한의 인원으로만 그룹 결성을 진행한다.
- 현재까지 그룹에 포함된 인원이 탐색된 모험가의 공포도보다 크기만 하면, 바로 그룹을 결성해버린다.
댓글