[BOJ] 백준 16401 과자 나눠주기

태환·2024년 2월 3일
0

Coding Test

목록 보기
45/151

📌 [BOJ] 백준 16401 과자 나눠주기

📖 문제

📖 예제

📖 풀이

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

start = 1
end = max(snack)

result = 0
while start <= end:
  mid = (start + end) // 2
  cnt = 0
  for i in snack:
    cnt += i // mid
  if cnt >= M:
    start = mid + 1
    result = mid
  else:
    end = mid - 1

print(result)

나눠줄 과자의 최대 길이를 mid로 설정하여 이분 탐색을 수행한다.
해당 길이에 대해 몇명의 조카들에게 나눠줄 수 있는지 확인하여
만약 M보다 더 많은 조카들에게 나눠줄 수 있다면 과자의 최대 길이를 높이고,
M보다 더 적은 조카들에게 나눠줄 수 있다면 과자의 최대 길이를 줄이는 방향으로 이분 탐색을 수행한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글