[BOJ 1654 / 파이썬] 랜선 자르기

0. 문제 링크

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

1654번: 랜선 자르기

1. 문제

2. 해결 알고리즘

이분 탐색

3. 이 문제의 특징

이 문제의 핵심은 최대 길이의 랜선으로 뽑는 것이다.

예를 들어서 603m의 랜선을 3개로 자른다고 했을 때 200m도 3개, 201m도 3개이다.

여기서 문제는 201m 200m 자른 결과 값이 똑같이 3개인데 어떻게 구분하냐는 것이다.

답은 right 값에 있다.

right 로 설정된 값은 이전 반복문에서 조건 값을 통과 하지 못한 (이분 탐색의 중간값) 바로 아래의 수이다.

그렇기에 만약 이번 반복문에서 통과가 되었다면, right 가 최대 값 일 것이다.

이 문제의 특징은 보통 (이분 탐색의 중간값)으로 비교하는 문제가 많은데 이 문제는 최대값이라는 조건 때문에

right 에 신경을 쓰지 못하고 이분탐색의 중간값으로 출력한다면 틀릴 것이다.

4. 코드

import sys

input = sys.stdin.readline

def main():
	K, N = map(int, input().split())
	
	arr = [int(input()) for _ in range(K)]
	
	left = 1
	right = max(arr)
	mid = (left + right) // 2
	
	while left <= right:
		mid = (left + right) // 2
		
		count = 0
		for n in arr:
			count += n // mid
			
		if count >= N:
			left = mid + 1
		else:
			right = mid - 1
			
	print(right)
	
main()