[백준] 1654번 랜선 자르기

<문제>

 

 

 

 

 

 

<입력/ 출력>

 

 

 

 

 

 

<풀이>

이진 탐색을 이용해서 랜선이 조건을 만족하는 최대 길이를 구해야 한다.

N개의 랜선을 만들어야 하므로, mid를 기준으로 랜선을 자를때 나오는 count값을 세어서,

count 값이 N개의 값보다 더 크다면, 더 랜선의 길이를 늘릴 수 있으므로, start = mid + 1로 조건을 바꾼다.

count 값이 N개의 값보다 더 작다면, 랜선의 길이를 줄여야 하므로, end = mid - 1로 조건을 바꾼다.

 

 

 

 

 

 

<코드>

k, n = map(int, input().split())
array =[]

for i in range(k):
    array.append(int(input()))

start = 1
end = max(array)

while(start <= end):
    mid = (start + end)//2
    count = 0
    for i in range(k):
        count += array[i] // mid
    if count >= n:
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

 

 

 

<결과>