https://www.acmicpc.net/problem/1654
initial
Typical binary search question where you are guessing the value. It is always the start<end or start<=end that confuses me. But we want to record the maximum length of the cut-cables so we want to cut as long as possible. Our condition is if total pieces that we have cut are greater or equal to target n, we record that guess value as our answer. The final iteration of search will give us the answer by updating guess value to our answer variable.
start has to be at least 1, not 0 (divisionby0error wil be caused)
revisit may 21st 25
question said N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. So the condition should be if(count>=n) cuz even if count is bigger than n, it is still valid.
solution
import sys
input = sys.stdin.readline
k, n = map(int, input().split())
lst=[]
for _ in range(k):
lst.append(int(input()))
start, end = 1, sum(lst)
ans = 1
while start < end:
mid = (start + end) // 2
tmp = 0
for i in lst:
tmp += i // mid
if tmp >= n:
ans = mid
start = mid +1
else:
end = mid
print(ans)complexity
binary search is log n but inside then, i iterate through i so n log n time?
n space cuz of lst
yes
