백준_1654_랜선 자르기(이분 탐색)

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

1654번: 랜선 자르기

해결 방법

> left는 1(문제에서 최소 길이가 1이라고 함), right는 주어진 랜선 중 최대값

> 이분 탐색을 돌린다.

> right를 출력한다.

 

Right를 출력하는 이유

1. 이분 탐색을 돌릴 때 조건을 left <= right로 주었다.(right가 left보다 작아진 첫 시점이 출력시점)

2. 문제 조건 중 N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

    2- 1. 이분 탐색을 돌리는 중에 N개보다 많이 만들어질 수도 있다. 하지만 2 - 2조건에 의해 정답이 아닐수 있다.

    2- 2. 문제 조건 중 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

코드

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

 

cable = list()

for i in range(k):

    cable.append(int(input()))

 

left = 1

right = max(cable)

 

while left <= right:

    mid = (left + right) // 2

    tmp = 0

    for i in cable:

        tmp += i // mid

    if tmp < n:

        right = mid - 1

    else:

        left = mid + 1

 

print(right)