[그리디 5] 모험가 길드

Tino-Kim·2023년 1월 5일

그리디 코딩테스트

[Coding Test] 준비하기

목록 보기

5/20

[그리디 5] 모험가 길드

미니 예제 1

1. 문제 설명하기.

모험가 N명을 공포도에 따라서 최대 그룹으로 나누는 문제이다. ~~주의할 점은 공포도 수치만큼 모험가를 묶어야 된다는 점이다. 그러므로 공포도가 높은 모험가부터 묶어야 하기 때문에,~~ 가장 좋은 것을 택해야 하는 그리디 문제이다.

모든 카드를 이용하지 않아도 된다. 그러므로 최대 그룹 수를 만들기 위하여 공포도 수치가 가장 낮은 카드부터 그룹으로 지정해야 한다.

2. 문제 풀이하기.

N=5이고, 각 모험가의 공포도가 [2, 3, 1, 2, 2] 이다.

Step 1. 모험가의 공포도를 오름차순으로 나열한다.
Step 2. 무한 반복문을 돌리고, 공포도의 최대가 공포도 길이보다 큰 경우, 반복문의 종료 조건으로 걸어준다.
Step 3. 규칙에 따라 그룹으로 묶은 뒤에 공포도를 재설정하고 그룹 수를 세어준다.

# 미니 예제 : N=5, [2,3,1,2,2]

N=5
data=[2,3,1,2,2]
count=0

data.sort() # sort에는 내림차순 매개변수가 존재한다.

while True:
    if min(data) in data:
        data=data[min(data):]
        count+=1
    if max(data)>len(data):
        break
    
print(count)

최적의 일반화

1. 문제 설명하기.

N과 각 모험가의 공포도를 따로 받아서 문제를 진행한다. 위의 내용과 동일하다. 각 모험가의 공포도는 리스트에 받고 data 라고 하자.

2. 문제 풀이하기.

여기서 주의할 점은 나는 최소값을 이용하여 각 모험가의 공포도를 재설정하였다.

예를 들면 최소값이 3인 경우, 3명의 모험가가 필요하기 때문에 그 모험가를 1개의 집단에 넣을 수 있다. 그러므로 남은 공포도로 다시 집단을 구성해야하기 때문에, 최소값을 인덱스로 사용하여 이미 이룬 집단의 구성원들을 날려버렸다.

# 최적의 일반화

N=int(input())
data=list(map(int, input().split()))
count=0

data.sort() # sort에는 내림차순 매개변수가 존재한다.

while True:
    if min(data) in data:
        data=data[min(data):] 
        count+=1
    if max(data)>len(data):
        break
    
print(count)

~~내가 풀이한 일반화는 좋지 않은 일반화이다. 왜냐하면 반복문 빠져나오는 조건이 안 좋기 때문이다.~~

예를 들자면 [1,2,2,2,2,4]인 경우 위의 코드로 [1]이 하나로 묶이고 [2,3]도 하나로 묶일 수 있으나, [2,2] 또한 원래 묶일 수 있으나 4>3 이기 때문에 무한 반복문이 끝나버린다. 따라서 이런 경우에는 원하는 답과 다른 결과가 나올 수 있다. 그러니 책에 나와있는 풀이로 이해를 하자.

3. 책에 나와있는 최적의 일반화

기준	나의 풀이	책의 풀이
변수 설정	그룹 수	그룹 수와 모험가의 수
공포도 재설정	인덱스 이용하기.	모험가의 수가 공포도 이상임을 이용한다.

모험가의 수가 공포도가 동일한 경우, 그룹으로 지정하는 것이 최대 그룹 수로 묶는 방법이다. 그리고 공포도와 모험가의 수가 최대 그룹을 묶는 중요한 요인이기 때문에 2개의 변수를 이용했다.

# 책에 나와있는 일반화 (숫자 대입한 코드)

N=5
data=[2,3,1,2,2]

result=0 # 총 그룹의 수
count=0 # 현재 그룹에 속한 모험가의 수
data.sort() # 오름차순 정렬하기. [1,2,2,2,3]으로 정렬하기.

for i in data: # 각 모험가의 공포도를 하나씩 가져오기.
    count+=1 # 모험가 +1명 포함시키기. 
    if count>=i: # 공포도 기준으로 그룹핑하기 때문이다.
        result+=1 # 그룹으로 설정하기.
        count=0 # 모험가의 수 초기화하기.

print(result)

# 책에 나와있는 일반화
# 변수를 2개를 이용 : 현재 그룹에 속한 모험가 수, 최대 그룹 수

N=int(input())
data=list(map(int, input().split()))

result=0
count=0
data.sort()

for data in data: # 1 > 2 > 2 > 2 > 3 순으로 등장한다.
    count+=1
    if count>=data:
            result+=1
            count=0
            
print(result)