백준_1654_랜선 자르기

문제

1654번: 랜선 자르기

풀이

해당 문제는 이분 탐색으로 해결할 수 있다. 

1. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 크거나 N과 같다면 랜선의 길이가 속하는 구간 [start, end]를 [(start, end)/2, end]로 줄인다.

2. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 작다면 랜선의 길이가 속하는 구간 [start, end]를 [start, (start, end)/2]로 줄인다.

 

구간의 크기가 1이 될 때까지 이분 탐색을 계속하여 충분히 작은 범위을 구한다. 

end일 때 계산한 랜선의 개수 number가 필요한 랜선의 개수 N와 같거나 크다면 end가 답이 되며, 그 이외의 경우 start가 답이 된다.

코드

K, N = map(int, input().split())
arr = [int(input()) for i in range(K)]

# 이분 탐색
start, end = 1, max(arr) # 랜선의 길이
while end-start>1 :
    p = int((start+end)/2)
    number = sum([int(arr[i]/p) for i in range(K)]) # 랜선의 개수
    if number>=N : start = p
    else : end = p

# 답 찾기
number = sum([int(arr[i]/end) for i in range(K)])
if number>=N : print(end)
else : print(start)