[그리디 알고리즘] - 문제: 모험가 길드

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2&t=1s

출처: 동빈나 유투브

다음의 강의를 참고했음을 밝힙니다. 

---

<문제> 모험가 길드

 

출처: 동빈나 유투브

내가 작성한 코드

n = input()
values = list(map(int, input().split()))
# print(values)
values.sort()
print(values)
#%% md
* 오 이번 문제는 뭔가 감이 오지 않는다. 
* 최대 공약수도 아니고 최소 공배수도 아닌.. 이걸 컴퓨터로 풀 수 있는 문제인가? 하는 생각이 들었다. 
* 여행을 떠날 수 있는 그룹의 최대수라고 하면, 가장 큰 수를 기준으로 다 넣은 다음에 개수를 구해야 하나? 
* 정렬한 다음에 어떻게 풀어야 할지 감이 오지 않는다..

---

 

문제 해결 아이디어

 

출처: 동빈나 유투브

답안 예시

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹의 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인: 1->2->2->2->3
    count += 1 # 현재 그룹의 모험가를 하나씩 포함시키기: 1->1->2->1->2
    if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성: 1, 1 -> 1, 2 -> 2, 2 -> 1, 2 -> 2, 3
        result += 1 # 총 그룹의 수 증가시키기: 1->2
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
print(result) # 총 그룹의 수 출력
#%% md
* 하나씩 코드를 뜯어보면 어떻게 동작하는지 알 수 있었음. 
* 하지만 이걸 생각해서 풀어야 된다? 당체 어떻게 할지를 모르겠음. 
* 코드가 어려운 코드는 아닌데.. 
* 여기서 중요한 건 result(총 그룹의 수), count(현재 그룹에 포함된 모헙가의 수)를 각각 선언하고 이를 활용하는 것이다
* 그리고 count가 i(공포도)보다 크면 result의 수를 증가시킨 뒤, count = 0으로 바꾸고 다시 처음부터 시작
* 만약에 count가 i보다 작으면 그냥 count를 키워가는 것
* 이거 코드는 쉬운데 말이여~~~ 내가 푸려고 하면 이게 안된다 이 말이여~~
* 연습이 답이다~!

 

---

https://github.com/Park-Minjoo/CODINGINTERVIEW_PRACTICE/tree/main/Algorithms