[Python] 백준 1654. 랜선 자르기

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

1654번: 랜선 자르기

이분탐색 문제. 이분탐색으로 찾아야 할 값은 '랜선의 길이'이고, 이분탐색의 기준은 '랜선의 개수'가 된다.

 

랜선의 길이 최솟값은 1, 최댓값은 주어진 랜선 길이로 정한 뒤

mid = (최솟값 + 최댓값) // 2로 잘라낼 길이를 정하고, 랜선 길이에서 mid만큼 잘라낼 경우 몇 개가 나오는지 합계를 구하면 된다.

 

	import sys
	k, n = map(int, sys.stdin.readline().split())
	arr = []
	for _ in range(k):
	arr.append(int(sys.stdin.readline()))
	lower_bound, upper_bound = 1, max(arr)
	result = 0
	while lower_bound <= upper_bound:
	# 몇 cm의 크기로 잘라낼 것인지.
	mid = (lower_bound + upper_bound) // 2
	# 해당 크기로 잘라냈을 때 몇 개의 랜선이 모이는지
	cut_sum = sum([(i // mid) for i in arr])
	# 잘라낸 개수가 기준보다 많다면, 더 큰 단위로 잘라서 개수를 줄여도 된다.
	if cut_sum >= n:
	result = mid
	lower_bound = mid + 1
	# 잘라낸 개수가 기준보다 적다면, 더 작은 단위로 잘라서 개수를 늘려야 한다.
	elif cut_sum < n:
	upper_bound = mid - 1
	print(result)

view raw [백준] 랜선 자르기.py hosted with ❤ by GitHub