[ 이코테 ] 모험가 길드 - 파이썬(Python)

싱가·2023년 3월 3일
0

문제

  • 한 마을에 모험가 N명
  • 모험가 N명은 각각 '공포도'가 존재
  • 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여
  • 최대 만들 수 있는 그룹의 수
  • 또한, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요 X

입력 예시

5
2 3 1 2 2

출력 예시

2

아이디어

  • 최대 만들 수 있는 그룹의 수 → 최소한의 인원으로 그룹 참여

예시 풀이

  1. 공포도 X [ 2, 3, 1, 2, 2 ] 를 오름차순으로 정렬 하여 [ 1, 2, 2, 2, 3 ] 으로 만든다.
  2. 처음 모험가는 공포도가 1이므로 단일 팀 구성
  3. 두 번째 모험가는 공포도가 2이므로 세 번째 모험가와 함께 팀 구성
  4. 네 번째 모험가의 공포도는 2, 마지막 모험가는 3이기에 팀 구성 불가
  5. 총 최대 2개의 그룹 구성

코드

n = 5
x = [1, 2, 3, 3, 4]
x.sort()

cnt = 0  # 그룹에 참가한 모험가 수
result = 0  # 그룹 수

for i in x:
    cnt += 1
    
    if cnt >= i:
        result += 1
        cnt = 0

print(result)

참고 영상

https://www.youtube.com/watch?v=_TG0hVYJ6D8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=13&t=823s

0개의 댓글