python | 모험가길드 | 그리디(greedy)

대표적인 그리디 문제 중 꽤 쉬운 난이도인 모험가길드 문제를 풀어보겠다.

 

 

📒 문제

---

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데,'공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다.

N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 모험가의 공포도가 다음과 같다고 가정합시다.

2 3 1 2 2

이 경우 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있습니다. 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

 

 

🤸‍♀️ 문제 분석

---

문제의 조건 중 마지막 문장이 중요한 것 같다.

몇 명의 모험가는 마을에 남아있어도 되며, 출발하는 여행의 그룹 수를 최대로 만들 것!

그렇다면,
그룹의 단위가 작을 수록 여행 그룹 수가 많아지기 때문에,

그룹의 단위가 적기 위해서는 공포도가 낮은 모험가 위주로 구성되어야 한다.

 

[1, 2, 3, 4, 3, 4] => [1] [2, 2] [3, 4, 3, 4]

이런 식으로 숫자가 작을 수록 그룹의 단위가 작아진다. 

 

그러므로, 마을에 남는 모험가는 되도록 공포도가 높은 모험가를 남게 한다.

 

이를 코드로 구현하기 위해서는

💡각 모험가의 공포도를 오름차순으로 정렬하여, 공포도가 낮은 순부터 그룹을 결성하여 여행을 떠나보낸다.

 

 

🧮코드

---

# 모험가 길드

# n : 마을에 있는 모험가의 수
# x : 각 모험가의 공포도
# x의 공포도를 가진 사람은 반드시 x명 이상의 모임이 형성되었을 때 여행 출발 가능
# 여행을 떠날 최대한의 그룹 수, 모든 모험가를 그룹에 넣을 필요 X
# ==> 최대한의 그룹수이고 모든 모험가가 갈 필요는 없기 때문에 공포도가 낮을 모험가 순으로 출발하도록 전략 짜자

n = int(input())
explorers = list(map(int, input().split()))

# 오름차순 정렬
explorers.sort()

# group : 여행을 떠나기 전 대기 그룹
group = []
# cnt : 여행을 떠나는 총 그룹 수
cnt = 0

# 모험가 한명씩 탐색
for e in explorers:
    # 그룹에 넣기
    group.append(e)
    
    # 그룹의 인원수와 현재 모험가의 공포도 비교
    # 만약 그룹의 인원수가 모험가의 공포도보다 크거나 같다면 여행 출발 가능
    if len(group) >= e:
        # 여행을 보낸다 = 대기 그룹을 비운다
        group = []
        # 여행 떠나는 그룹의 수 +1
        cnt += 1

print(cnt)

 

---

📎TMI..

사실 group을 리스트로 꼭 선언할 필요 없이,

int 형으로 만들어서 아래와 같이 group의 member수와 현재 모험가의 공포도를 비교한 뒤 다시 0으로 초기화해줘도 되지만,

왠지 여행떠나는 그룹의 목록을 보고싶어 리스트형태에 담은 후 초기화하는 방법을 선택했다.

 

n = int(input())
explorers = list(map(int, input().split()))

# 오름차순 정렬
explorers.sort()

# member : 여행을 떠나기 전 대기 그룹의 인원수
member = 0
# cnt : 여행을 떠나는 총 그룹 수
cnt = 0

# 모험가 한명씩 탐색
for e in explorers:
    # 그룹에 넣기
    member += 1
    
    # 그룹의 인원수와 현재 모험가의 공포도 비교
    # 만약 그룹의 인원수가 모험가의 공포도보다 크거나 같다면 여행 출발 가능
    if member >= e:
        # 여행을 보낸다 = 대기 그룹을 비운다
        member = 0
        # 여행 떠나는 그룹의 수 +1
        cnt += 1

print(cnt)