[그리디] 01.모험가 길드 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

그리디 개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기
• 다양한 알고리즘에 두루 사용    # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

빈출유형

거스름돈 문제

• 거슬러 줘야 할 동전의 최소 개수 찾는 문제
• 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업

1이 될 때까지

• N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산
• 최대한 많이 나누기가 문제 해결 아이디어

 

문제

 

해설

공포도가 가장 낮은 모험가부터 하나씩 확인

현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 이를 그룹으로 설정

공포도가 오름차순으로 정렬되어 있음 → 항상 최적의 해

 

풀이

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)        # 총 그룹의 수 출력

 

해석

 

변수 : 모험가 수 N, 공포도 리스트 data, 그룹 수 result, 현재 모험가 수 count

 

1. 모험가 수 N, 공포도 리스트 data 입력받기

2. 공포도 리스트 data 정렬 : 오름차순

3. 그룹 수 result, 현재 모험가 수 count 변수 정의

------------------------------- 공포도 리스트 반복문 : i in data  -------------------------------

4. 현재 모험가 수 count += 1

5. 조건문 : (현재 모험가 수 count) >= (현재 공포도 i)

ㄴ 그룹 생성 완료 : 그룹 수 result += 1

ㄴ 현재 모험가 수 count 초기화 : 0