Chapter 11.그리디 문제

Q01. 모험가 길드

✔️문제 유형

그리디

✔️문제

• 모험가 N명

• 모험가 길드에서 N명의 모험가를 대상으로 ‘공포도’ 측정, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력 떨어짐

• 모험가 그룹 구성 : 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행 가능

• 최대 몇 개의 모험가 그룹을 만들 수 있는가?

✔️입력 조건

첫째 줄에 모험가의 수 N이 주어집니다. (1 <= N <= 100000) 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.

✔️출력 조건

여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

✔️입력 예시

5

2 3 1 2 2

✔️출력 예시

2

---

내 풀이

💡아이디어
o 공포도가 큰 친구부터 그룹에 넣자 -> 공포도가 작은 애들은 적은 수로 많은 그룹 형성 가능하기 때문!!

N = int(input())
if (1 <= N <= 100000):
  members = list(map(int, input().split()))
  if (max(members) <= N):
    team_num = 1
    members.sort(reverse=True)
    # 팀 나누기
    chef = max(members)
    chef_index = members.index(chef)

    while True:
      next_chef_index = chef_index + chef
      chef = members[next_chef_index]
      chef_index = next_chef_index

      team_num += 1

      if (chef_index + chef == len(members)):
        break

    print(team_num)

---

답안

💡아이디어
o 공포도를 기준으로 오름차순으로 정렬 수행
o 공포돠 낮은 모험가부터 하나씩 확인하며, 그룹에 포함될 모험가의 수 계산!!
o 현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도 라면 그룹 결성 가능!!

---

💬개선할 점
o 나의 답변은 아예 틀림.
-> 큰 친구부터 하면 가장 적은 수의 그룹을 결성하게 되는거임. 공포도가 낮은 순부터 하면 공포도가 높은 친구는 놔두고 갈 수 있음!!