2-5. 이코테 - Greedy - 모험가 길드

• 링크 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2&t=1008s

---

• (중요)(Tip) 그리디 문제의 경우, 문제에서 반드시 순차적으로 처리해야한다같은 내용 없으면 정렬(오름차순/내림차순)하는게 유리할 때도 있음을 알아두자

• 그리고 본 문제에선 "최대 몇 개의 모험가 그룹을 만들 수 있느냐"가 핵심이기 때문에, 그룹에 들어오는 사람을 최소 인원으로 맞춰줘야 답이 나온다

  • 예를 들어서 [2 3 1 2 2]의 경우에
  • 한 그룹에 3명 이상 들어가도 된다면 {1, 2, 2, 2, 3}이 한 그룹으로 1그룹만 생겨도 되는데
  • 최대한 몇 개를 만들 수 있냐가 중요하기 때문에 {1}, {2, 2}, {나머지 안되므로 버림} 이렇게 되어야 한다
  • 즉, 공포도가 1인 사람은 그룹 내에 최소 인원 1명만, 공포도가 2인 사람은 그룹 내에 최소 인원 2명만, 공포도가 3인 사람은 최소 인원 3명만 ... 구성해야 최대 그룹 수를 만들 수 있음

---

''' 내가 푼 - 처음 시도 (잘못된 답-이유 : 입력된 순서 그대로 구성하는줄 앎) '''
def sol(n,arr):
    answer = 0
    group_size = 0
    
    for i in range(n):
        print(group_size)
        if arr[i] == 1: 
            group_size += 1
            
        elif group_size <= arr[i]:
            group_size += 1
            
        else:
            group_size = 0
            answer +=1
    
    return answer



n = int(input())
arr = list(map(int, input().split()))
print(sol(n, arr))

''' 내가 푼 - 추가 테스트 케이스 보려다가 문제해결 아이디어 보고 푼 (정렬 사용) '''
def sol(n,arr):
    answer = 0
    group_size = 0
    
    for i in arr:
        if i == 1: 
            group_size = 0
            answer +=1
            print('---------')
            
        elif group_size < i:
            group_size += 1
            
        else:  # ( group_size >= i)
            group_size = 0
            answer +=1
            print('---------')
        
        print(i, '    ', group_size, '    ', answer)
    
    return answer

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
print(sol(n, arr))

''' 동빈나 - 솔루션 '''

def sol(n,arr):
    answer = 0
    group_size = 0
    
    for i in arr:
        group_size += 1
        
        if group_size >= i:
            answer += 1
            group_size = 0
    
    return answer

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
print(sol(n, arr))