[백준 / 파이썬] 16401. 과자 나눠주기

https://www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

🎉 문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

 

 

 

 

🎉 풀이

✅ 전형적인 이분탐색 문제

✅ 조건에서 과자의 길이는 최소 1부터 주어진다고 함

'질문하기'에 반례로 3 3 / 1 0 1 이 나와있는데 이거 생각하는 순간 바로 틀렸습니다 x100 됨.. 그냥 1부터 주어지니까 과자 길이가 0인 경우 생각하지 마세요

 

 

 

 

🎉 코드

 

n, m = map(int, input().split()) #조카의 수, 과자 개수

array = list(map(int, input().split())) # 과자들의 길이를 담은 배열

array.sort()

left = 1 #과자의 최소 길이=1 (조건에 명시)
right = max(array) #제일 긴 과자의 길이 = 조카한테 나눠줄 수 있는 최대 과자길이

result = 0 
while left <= right:
  mid = (left+right)//2

  cnt = 0 #과자 개수
  
  for i in array:
    cnt += (i//mid) #mid길이의 과자를 몇 개까지 나눠줄 수 있는지

  if cnt >= n:
    left = mid+1 #시작값 증가
    result = mid #정답 갱신
  else:
    right = mid-1 #끝값 감소

print(result)