백준 2792번: 보석상자 (파이썬)

 

조건 :

  한 아이에게 같은 보석만을 준다

  보석을 안줘도 상관이 없음

찾아야 할 결과 :

  가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수

 

알고리즘 분류 : 이분 탐색

이걸 어떻게 이분 탐색으로 풀어낼 수 있나 하는 고민이 들었다 각자 가져가는 보석의 개수가 다른데 식을 어떻게 짜는 건지 알 수가 없었다.

보석을 최대로 많이 가져갈 수 있는 수는 보석 리스트에서 제일 큰 수와 같으므로 max = max(보석 리스트)

 

N,M = map(int,input().split())

# 보석 담을 리스트
M_list = list()
for i in range(M):
  M_list.append(int(input()))

# 정렬
M_list.sort()

# 한 명이 가질 수 있는 최소값, 최대값
min = 1
max = max(M_list)

while(min<=max):
  mid = (min + max) // 2
  total = 0
  
  # 보석을 나눠가지는 학생 수 카운트
  for i in M_list:
    if i % mid == 0:
      total += i // mid
    else:
      total += (i // mid) + 1
      
  if total > N:
    min = mid + 1
  else:
    max = mid -1
    
print(min)

제일 애를 먹었던 부분은  for문을 작성하는 부분

예제는 통과해서 되는 줄 알았는데 계속 틀려서 쉽지 않았다