백준1654)랜선 자르기-python

 

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

1654번: 랜선 자르기

 

 

n,m = map(int,input().split())

arr = []
for _ in range(n):
  a = int(input())
  arr.append(a)


start = 1
end = max(arr)


while start <= end:
  mid = (start + end) // 2

  line = 0
  for i in arr:
    if i >= mid:
      line += i // mid

  if line < m:
    end = mid - 1
  else:
    start = mid + 1

print(end)

사실 문제는 간단하다.

start는 1,

end는 max값으로 설정한 다음

while문으로 진입한다.

 

while문에선 start와 end의 중간값을 구하고 그 중간값으로 선들을 잘라 개수를 구한다.

만일 개수가 적을 경우 end = mid -1

개수가 만들경우 start = mid + 1

만일 개수가 같더라도, start는 계속 갱신되므로 end은 정답으로 고정된다.