모험가 길드 문제는 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다.
첫째줄에 n이 주어지고 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어집니다.
모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.
여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.
<나의 풀이>
from collections import deque
if __name__ == '__main__':
n = int(input())
list1 = list(map(int, input().split()))
list1.sort(reverse=True)
arr = deque(list1)
result = 0
while arr:
x = arr[0]
if x <= len(arr):
for i in range(x):
arr.popleft()
else:
break
result += 1
print(result)나의 풀이는 잘못 되었습니다. 해당 알고리즘은 그리디가 적용되어야 됩니다. 하지만 저는 가장 공포도가 높은 모험가를
먼저 파티에 넣는 식으로 하였기 때문에 그룹의 수는 가작 적은 그룹의 수가 리턴 될 것입니다. 그것을 알고도 위와같은 알고리즘을 사용한 것은 가장 큰 값을 기준으로 해야 나중에 뒤에서 더 큰 공포를 가진 모험가가 나타나서 위 조건을 이탈하는 케이스를 생각했기 때문입니다.
아래는 정답입니다.
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
정답을 보면 if count >= i:
라는 조건이 있습니다. 해당 조건 덕분에 뒤에서 갑자기 공포도가 큰 모험가가 포함 되어도 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날수 있는 조건을 만족할 수 있습니다.
'알고리즘' 카테고리의 다른 글
| [이코테] 문자열 재정렬 (0) | 2022.01.04 |
|---|---|
| 볼링공 고르기[이코테] 그리디 (0) | 2022.01.03 |
| 백준 피보나치의 수5 (0) | 2021.12.29 |
| 백준 설탕 배달 dp (0) | 2021.12.26 |
| 떡복기 떡 만들기 이진 탐색 (0) | 2021.12.20 |
