이미 가지고 있는 랜선의 개수 K개를 일정 길이만큼 잘라서, 필요한 같은 크기의 랜선 N개를 만들어야 하는데, 이 때 만들 수 있는 최대 랜선의 길이를 구하는 문제이다.
문제는 달라 보이지만 이해하고 나면 결국 같은 이진 탐색 활용 문제이다.
# 랜선 자르기
k, n = map(int, input().split()) # 가지고 있는 랜선 개수, 만들어야 할 랜선 개수
lans = [] # 가지고 있는 랜선들
for _ in range(k):
lans.append(int(input()))
start = 1 # start 포인터를 1로 설정
end = max(lans) # end 포인터를 가장 긴 랜선 길이로 설정
while start <= end:
mid = (start + end) // 2 # 중간값(랜선의 최대 길이) 설정
lan = 0 # 현재 랜선 길이
for i in lans:
lan += (i // mid) # 각 랜선의 길이를 설정한 랜선의 최대 길이로 나눠준다. (나오는 값 -> 만들 수 있는 랜선의 개수)
if lan >= n: # 총 만들 수 있는 랜선 개수가 만들어야 할 랜선 개수보다 같거나 클 경우
start = mid + 1 # start 포인터를 증가
else: # 총 만들 수 있는 랜선 개수가 만들어야 할 랜선 개수보다 작을 경우
end = mid - 1 # end 포인터를 감소
print(end)start 포인터를 1로 설정한 이유:
예를 들어,
랜선들이 [802, 743, 457, 539] 일 경우,
n = 802인 경우(즉, 랜선 802개를 만들어야 하는 경우)가 있을 수 있다.
그럼 이때 랜선의 최대 길이는 1이 된다.
