[파이썬 알고리즘] 모험가 길드 문제 풀이

❓ 문제

---

✏ 나의 풀이 - 오답

---

n = int(input())
# 공백을 기준으로 나눠 배열에 저장
m = [int(x) for x in input().split()]
g = 0

while True:
    if n < max(m):
        print(g)
        break
    else:
        g += 1
        n -= max(m)
        m.remove(max(m))

💡 문제 해결 아이디어

---

오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인한다.

앞에서부터 공포도를 하나씩 확인하며 ‘현재 그룹에 포함된 모험가의 수’가 ‘현재 확인하고 있는 공포도’보다 크거나 같다면 이를 그룹으로 설정하면 된다.

이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다.

✔️ 파이썬 답안 예시

---

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) # 총 그룹의 수 출력

💬 풀이 평가

---

모험가가 꼭 그룹에 포함되지 않아도 된다는 점을 생각하지 못해, 공포도가 높은 모험가부터 그룹을 만드는 오답이 나온 것 같다.

Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 영상과 교재를 참고하였습니다.