BaekJoon1654_랜선 자르기

문제

풀이

이 문제도 보자마자 실행시간은 2초인데 입력값이 큰거로 보아 이진탐색을 사용해야 될 것같아 먼저 이진탐색으로 풀이를 진행했다.
1. n,k를 입력받는다.
2. 리스트를 입력받고 정렬한다.(이진탐색을 사용하는 문제지만 리스트 안의 값들이 기준이 되지 않기 때문에 정렬을 꼭 할 필요는 없다.)
3. 랜선의 길이는 정수이므로 start는 1 end는 리스트(랜선들의 길이)의 최댓값을 할당한다.
4. 기존의 이진탐색을 하듯이 while문을 돌린다. while문을 돌리면서 temp를 두고 랜선 리스트를 돌리면서 mid값보다 크면 각 리스트의 인덱스 값을 mid로 나눈뒤 몫을 temp에 더한다.
5. temp 값이 k보다 크거나 같으면 answer = temp를 한다.
6. 랜선은 K개 이상이면서 랜선의 길이도 최대여야 하므로 temp 값이 k보다 크면 start = mid + 1, 반대면 end = mid - 1을 한다.
7. while 문이 종료되면 answer가 답이된다.

풀이 코드

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

list = []
for i in range(n):
   list.append(int(input()))

list.sort()
start = 1
end = max(list)
answer = 0

while start <= end:
   temp= 0
   mid = (start + end) // 2
   for i in list:
       if i >= mid:
           temp += ( i//mid )
   if temp >= k:
       start = mid + 1
       answer = mid
   else:
       end = mid - 1
           
print(answer)