import sys
input=sys.stdin.readline
N,M=map(int,input().split())
L=[]
for i in range(M):
L.append(int(input()))
start=1 # mid 값이 0이 되는것을 막기 위해 1로 시작한다.
end=max(L) #end 값은 리스트 L의 최대값이다.
answer=0 #정답을 담을 변수
while start<=end:
mid=(start+end)//2
sum = 0
for i in range(len(L)):
sum+=L[i]//mid
if L[i]%mid!=0:
sum+=1
if sum>N:
start=mid+1
else:
end=mid-1
answer=mid
print(answer)처음에 문제를 이해했지만 어떻게 시작할지 많이 고민했다.
이분탐색 문제를 풀때 출발점은 시작점과 어떻게 끝점을 잡을것인가? 를 먼저 생각하는 것이다.
이것은 금방 해결할 수 있었는데 문제는 어떻게 탐색할것인가? 였다.
📌 KeyPoint: 보석을 동일한 개수로 최대한 많은 인원에게 나누어 줘야 개인이 가지는 보석의 수가 최소화된다.
이 문장이 가장 중요하다고 생각한다.
즉 어떤 보석이 주어졌을때 , mid 값으로 동일하게 나누어준다.
sum 변수는 특정한 mid 값으로 보석을 나누었을때 생기는 인원 수 이다.
이후 sum 의 값이 N보다 클때에는 start 값을 증가시켜 학생 개개인에게 나누어주는 보석수를 증가시키고 보석을 받은 학생수를 감소시킨다.
왜냐하면 sum 변수로 생긴 학생 수는 N 보다 클 수 없기 때문이다.
그리고 어떤 보석을 나눴을때 나머지가 0 이 아니면 남는 보석이 생겨 +1 을 해줘야 한다.
왜냐하면 남는 보석은 다른보석과 섞을수 없어 어쩔수없이 한사람에게 나머지를 몰아줘야한다.
문제에서 명시되어있듯이 한사람은 하나의 색깔의 보석밖에 갖지 못하기 때문이다.
이후 sum 변수가 N 보다 작거나 같으면서 mid 값이 가장 작을때 우리가 찾고자 하는 답이 나온다.
