백준 1654번: 랜선 자르기

백준 1654번: 랜선 자르기

1654번: 랜선 자르기

- 1789번: 수들의 합 문제와 매우 유사한 문제이다. 마찬가지로 이분탐색으로 접근하면 된다.

• start = 0, end = 2147483648(2^31 - 1) 으로 초기화한다. start가 end보다 작거나 같을 때까지 while문을 돌린다
• mid = (start + end) // 2
• rep은 각 랜선을 mid 길이만큼 잘랐을 때 나오는 랜선의 개수이다. for문을 통해서 long 리스트에 저장된 랜선들을 mid로 나눴을 때의 몫을 구한다
• rep이 n보다 크거나 같으면 mid가 작다는 것을 의미하므로 start = mid + 1 을 한다
• rep이 n보다 작으면 mid가 크다는 것을 의미하므로 end = mid - 1을 한다

아래는 파이썬 코드이다

 

	import sys
	k, n = map(int, sys.stdin.readline().split())
	long = []
	for _ in range(k):
	long.append(int(sys.stdin.readline()))
	start = 0
	end = 2147483648
	while start <= end:
	mid = (start + end) // 2
	rep = 0
	for _ in range(k):
	rep += long[_] // mid
	if rep >= n:
	start = mid + 1
	else:
	end = mid - 1
	print(start - 1)

view raw BOJ_1654.py hosted with ❤ by GitHub