 |
|
" 문제 "
한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했습니다.
...
공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
<입력 조건>
- 첫째 줄에 모험가의 수 N 이 주어집니다. (1 <= N <= 100,000)
- 둘째 줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.
<출력 조건>
- 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.
" 아이디어 "
공포도를 입력받은 travler 리스트를 오름차순으로 정리한 후,
공포도가 낮은 모험가부터 차례대로 그룹에 포함시키고, 그룹에 속한 마지막 모험가의 공포도를 기준으로 팀원 수를 만족시키면 그대로 해당 팀 구성을 마치고 다음 그룹을 구성한다.
예를들어 [ 2, 3, 1, 2, 2 ] 를 오름차순으로 정렬하여 [ 1, 2, 2, 2, 3 ] 로 만든다.
처음 모험가는 1이므로 단일 팀을 구성할 수 있게 된다.
다음팀원은 공포도가 2이므로 그 다음팀원까지 포함하여 [ 2, 2 ] 의 팀을 구성하게 된다.
마지막 남은 [ 2, 3 ] 은 3 때문에 팀을 구성할 수 없다.
이런 식으로 가장 공포도가 낮은 모험가부터 그룹을 결성하면, 최대한 많은 그룹을 결성할 수 있다.
" 코드 "
|
1
2
3
4
5
6
7
8
9
10
11
12
|
n = int(input())
travler = list(map(int, input().split()))
travler.sort()
cnt = sum = 0
for t in travler:
sum += 1
if sum == t:
cnt += 1
sum = 0
print(cnt)
|
cs |
" 참고자료 "
반응형
'알고리즘 > 기타' 카테고리의 다른 글
| [ 이것이 코딩테스트다 ] 만들 수 없는 금액 - 그리디 알고리즘 (0) | 2021.03.30 |
|---|---|
| [ 이것이 코딩테스트다 ] 곱하기 혹은 더하기 - 그리디 알고리즘 (0) | 2021.03.28 |
| [ 이것이 코딩테스트다 ] 1이 될 때까지 - 그리디 알고리즘 (0) | 2021.03.26 |
| [ 이것이 코딩테스트다 ] 숫자 카드 게임 - 그리디 알고리즘 (0) | 2021.03.26 |
| [ 이것이 코딩 테스트다 ] 큰 수의 법칙 - 그리디 알고리즘 (2) | 2021.03.26 |
