[이취코] 모험가 길드

출처 : 이것이 취업을 위한 코딩테스트다 with python p. 311

참고 : https://ssssol.tistory.com/49 (여기서 반례를 찾았다)

 

유형 : 그리디

 

1. 문제

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 첫째 줄에 모험가의 수 N이 주어지고, 둘 째줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지면, 각 자연수는 공백으로 구분한다.

단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 떄문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

 

예시

5
2 3 1 2 2

예시 출력

2

 

2. 내 코드

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

group.sort(reverse=True) # 내림차순 정렬

start = 0
_max = group[0]
end = start+_max
cnt = 1

while True:
    start = end
    _max = group[_max]
    end = start+_max
    cnt += 1

    if end >= n:
        break

print(cnt)

예를 들어 공포도가 3이라고 하면, 3이 속한 그룹은 3명 이상이 되야 하니깐 3명만 있으면 되겠다고 생각했다. 그래서 내림차순으로 정렬하고 큰 수부터 그 수에 해당하는 개수만큼 그룹을 만들어줬다. 하지만 답에서는 오름차순 정렬로 풀었고, 내 코드에서 오류를 발견했다.

 

예를 들어

6
4 3 3 3 3 2

위의 예시를 입력하게 되면 내 코드에서는 2가 나오게 된다. 앞에서 4명씩 끊어버리니깐. 하지만 실제로 구해보면 답은 1이 나와야하고 내 풀이가 잘못되었다는 것을 깨달았다.

 

그리고 방금 문제 조건을 다 안 읽었다는 것을 확인했다...(문제 좀 잘 읽자) 그룹 결성을 모두 다 안해도 되고 그룹 결성이 안되는 모험가가 남아도 된다는 조건..을 방금 봤다..

 

위의 코드를 수정했다. 그런데 최대 그룹 결성의 수를 구해야 하니, 애초에 오름차순으로 접근하는게 맞는 것 같다. 그리디 개념에 그게 맞기도 하고.. 반례를 찾은 건 아니지만, 잘못된 풀이인 듯하다.

## 수정
n = int(input())
group = list(map(int, input().split()))

group.sort(reverse=True) # 정렬
print(group)

start = 0
_max = group[0]
end = start+_max -1
cnt = 1

while True:
    start = end + 1
    _max = group[_max]
    end = start+_max -1

    if end >= n:
        break
    else:
        cnt+=1

print(cnt)

대략 코드를 설명하자면, start와 end로 그룹 결성의 시작점과 끝점(?)을 설정해두고 그 간격을 _max로 두었다. _max는 그룹 내에서 가장 큰 수를 가리킨다.

 

2. 코드

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)

최대 그룹 수 → 그리디 → 오름차순 정렬!